PadhaikoAll subjects

Solution of Non-Linear Equations

Numerical Methods (ENSH 252)

Open in the Padhaiko app

1.1 Errors and accuracy in numerical computations

In science and engineering, exact analytical solutions to non-linear equations such as or are rarely obtainable in closed form. Numerical methods yield approximate solutions using finite arithmetic operations, which inherently introduces numerical errors.

Definition

Absolute, Relative, and Percentage Errors

Let be the exact (true) value of a quantity and be its approximate value.

  1. True Error ():
  1. Absolute Error ():
  1. Relative Error (): Defined for as the ratio of absolute error to the magnitude of the true value:
  1. Percentage Error ():
  1. Approximate Relative Error (): When the exact value is unknown during an iterative method, consecutive approximations and give:

Sources of Numerical Error and Accuracy Concepts

Major Sources of Error in Numerical Computation
Error TypeOriginExample
Inherent (Input) ErrorUncertainty in physical measurements or model parametersUsing or noisy sensor readings
Truncation ErrorApproximating an infinite mathematical process by a finite number of stepsStopping the Taylor series after a finite number of terms; replacing a derivative by a finite difference
Round-off ErrorFinite word length (precision) of computers and calculatorsRepresenting or in 32-bit / 64-bit floating-point format
Definition

Accuracy, Precision, and Significant Digits


1.2 Bisection method

The bisection method (also called the binary chopping or interval halving method) is the simplest and most reliable bracketing method for finding a root of .

Theorem

Intermediate Value Theorem (Root Existence)

If is continuous on a closed interval and and have opposite signs, i.e.,

then there exists at least one real root such that .

Algorithm and Error Bound

  1. Choose two initial guesses and such that .
  2. Compute the midpoint of the current interval :
  1. Evaluate :
    • If (or and ), is the root; stop.
    • If , the root lies in , so set , .
    • Otherwise (), the root lies in , so set , .
  2. Repeat until the desired tolerance is reached.

After iterations (midpoints ), the interval width is halved each time, so the maximum possible error is:

To guarantee an absolute error at most , the minimum number of iterations required is:


1.3 Regula Falsi method and secant method

Both Regula Falsi (method of false position) and the secant method replace the curve over two points by a straight chord (secant line) and take its -intercept as the next approximation.

Regula Falsi (False Position) Method

Definition

Regula Falsi Formula and Bracketing

Given an initial bracket with , the straight line joining and crosses the -axis at:

Like bisection, the sign of determines which sub-interval retains the bracket:

Secant Method

Definition

Secant Method Formula

The secant method drops the bracketing requirement and always advances using the two most recent approximations and :

AspectRegula Falsi MethodSecant Method
Method ClassBracketing (closed) methodOpen-ended method
Sign ConditionRequires at every stepNo opposite-sign requirement
Update RuleKeeps the endpoint with opposite sign to Always keeps the two latest iterates
ConvergenceGuaranteed (order , linear)Not guaranteed, but superlinear () when it converges

1.4 Newton Raphson method

The Newton–Raphson method is the fastest standard open method for solving when is readily available.

Derivation via Taylor Series and Tangent Geometry

Expanding around by Taylor's theorem and truncating after the linear term:

Setting (the -intercept of the tangent line at ) gives the Newton–Raphson iteration formula:

Definition

Newton–Raphson Iteration Formula

Starting from an initial guess , compute successively:

Convergence and Failure Cases

Thus, the number of correct significant digits roughly doubles with every iteration.


1.5 Fixed point iteration method

The fixed-point iteration method (also called direct substitution or one-point iteration) solves by algebraically rearranging it into the form:

A root of is a fixed point of , meaning .

Definition

Fixed-Point Iteration Scheme

Given an initial guess and iteration function , generate the sequence:

Theorem

Sufficient Condition for Convergence

Let and be continuous on an interval containing the fixed point such that for all . If there exists a constant such that

then for any initial guess , the iteration converges uniquely to .


1.6 Comparison of the methods (Bracketing vs open-ended methods and rates of convergence)

Numerical root-finding methods fall into two broad categories: bracketing (closed) methods that trap the root inside a shrinking interval , and open-ended methods that extrapolate from one or two points without maintaining a sign-change bracket.

AspectBracketing MethodsOpen-Ended Methods
Initial RequirementTwo guesses with One guess (or two guesses for Secant), no sign check
Convergence GuaranteeAlways converges for continuous May diverge if initial guess is poor or
SpeedSlow (linear, )Fast when close to root (superlinear or quadratic )
Even-Multiplicity RootsFails (no sign change across root)Can locate multiple roots (though at reduced rate)
Summary Comparison of Single-Variable Root-Finding Methods
MethodIteration FormulaInitial GuessesOrder of Convergence ()Function Evaluations / StepMain Advantage / Drawback
Bisection (bracket) (linear, factor ) ()Always converges / very slow
Regula Falsi (bracket) (linear) ()Always converges / one endpoint may stagnate
Fixed-Point (linear if ) ()Simple to formulate / diverges if
Secant (no bracket) ()Fast without / may diverge
Newton–Raphson (quadratic) ( and )Fastest convergence / needs and good

1.7 Solution of system of non-linear equations

Many engineering problems require solving a simultaneous system of non-linear equations in unknowns. For two variables :

1.7.1 Direct approach

In the direct approach (successive substitution / multivariable fixed-point iteration), each equation is rearranged to isolate one variable:

Starting from an initial guess , iterates are computed in either:

1.7.2 Newton Raphson method

For the system and , first-order Taylor expansion about yields:

Definition

Multivariable Newton–Raphson and Jacobian Matrix

In matrix form , where is the Jacobian matrix evaluated at :

Solving by Cramer's rule (with determinant ):

and updating:

For a general non-linear system , solve the linear system (e.g., by Gauss elimination) and update . Like single-variable Newton–Raphson, the method exhibits quadratic convergence near a simple root when is non-singular.


Worked Out Examples

Example 1.1

1.1

Using the bisection method, perform iterations to find an approximate real root of

starting with the interval . Also determine the minimum number of iterations required to guarantee an error bound of .

Verifying the initial bracket: Evaluate at the endpoints of :

Since and is continuous, a real root lies in .

Performing five bisection iterations: At each step, compute and retain the sub-interval where changes sign:

  • First iteration (): , . Since , the new bracket is .
  • Second iteration (): , . New bracket: .
  • Third iteration (): , . New bracket: .
  • Fourth iteration (): , . New bracket: .
  • Fifth iteration (): , . New bracket: .
Bisection Iterations for f(x) = x^3 - 4x - 9
Iteration

Calculating minimum iterations for :

With , , and :

Rounding up to the next integer gives iterations.

Answer:

After iterations of the bisection method, the approximate root is (lying in ; exact root ). A minimum of iterations is required to guarantee an error bound .

Example 1.2

1.2

Find a real root of correct to decimal places using the Newton–Raphson method, starting with initial guess .

Setting up the Newton–Raphson formula: Let . Its first derivative is:

The Newton–Raphson update formula is:

Computing successive iterations from :

  • First iteration ():
  • Second iteration ():
  • Third iteration ():

Checking convergence: Comparing the last two iterates:

Both and round to to decimal places (and satisfies ).

Answer:

The real root of is , which is correct to decimal places.

Example 1.3

1.3

Solve the system of non-linear equations

using the Newton–Raphson method, starting from initial guess . Perform iterations.

Forming the residual functions and Jacobian matrix: Define:

Compute the partial derivatives:

First iteration from : Evaluate and the Jacobian entries at :

The Jacobian determinant is:

Solving for and :

Updating:

Second iteration from : Evaluate and :

Solving for the corrections:

Updating:

(A third iteration gives , rapidly converging to the exact solution .)

Answer:

After Newton–Raphson iterations, , converging to the exact root .


Exercises

Exercise — Solution of Non-Linear Equations

Question 1

Differentiate between truncation error and round-off error with an example of each. If is approximated using the first four terms of its Maclaurin series , compute the true absolute error, relative error, and percentage error.

Distinguishing truncation error and round-off error:

  • Truncation error occurs when an infinite mathematical procedure or series is terminated after finitely many steps (for example, truncating the Taylor series of or after terms, or replacing with ).
  • Round-off error occurs because computers and calculators represent real numbers using a finite number of digits/bits (for example, storing as or as ).

Computing the -term Maclaurin approximation for :

The true value (to decimal places) is .

Calculating absolute, relative, and percentage errors:

Answer:

Truncation error arises from cutting off an infinite mathematical process, whereas round-off error arises from finite-digit number representation. For the -term approximation of :

  • Absolute error:
  • Relative error:
  • Percentage error:
Question 2

Find a real root of using the secant method with initial guesses and . Perform iterations.

Evaluating the function at the initial guesses:

Applying the secant formula :

  • First iteration ():
  • Second iteration ():
  • Third iteration ():
Answer:

After iterations of the secant method, the approximate root is (exact root ).

Question 3

Use the Regula Falsi (false position) method to find the root of lying in up to iterations.

Checking endpoint signs on : Let :

Since , a root lies in .

Computing Regula Falsi iterations: Using :

  • First iteration ():

Since , the new bracket is .

  • Second iteration ():

New bracket: .

  • Third iteration ():
Answer:

After iterations of Regula Falsi, the approximate root is (with ).

Question 4

Rewrite in the fixed-point form . Verify that the fixed-point convergence condition holds near , and compute iterations starting from . Also state one advantage of open-ended methods over bracketing methods.

Checking the convergence criterion : Here , so:

At :

Since in a neighborhood of , the iteration is guaranteed to converge locally (in an oscillatory manner because ).

Computing three fixed-point iterations: Using :

Comparison note (open-ended vs. bracketing): Open-ended methods (such as Newton–Raphson and Secant) achieve higher orders of convergence ( or ) than bracketing methods () and can also find roots of even multiplicity where does not change sign.

Answer:

Since , the fixed-point iteration converges. The first three iterates are , , and . Open-ended methods converge faster (superlinear/quadratic) than bracketing methods when given a sufficiently close initial guess.

Question 5

Using the Newton–Raphson method for systems, perform iterations to solve

starting from .

Defining residuals and the Jacobian matrix: Let and . Then:

First iteration from :

Second iteration from :

Answer:

After Newton–Raphson iterations, the solution is (rapidly approaching the exact solution ).

Solution of System of Linear Algebraic Equations →