Solution of Non-Linear Equations
Open in the Padhaiko app1.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.
Absolute, Relative, and Percentage Errors
Let be the exact (true) value of a quantity and be its approximate value.
- True Error ():
- Absolute Error ():
- Relative Error (): Defined for as the ratio of absolute error to the magnitude of the true value:
- Percentage Error ():
- Approximate Relative Error (): When the exact value is unknown during an iterative method, consecutive approximations and give:
Sources of Numerical Error and Accuracy Concepts
| Error Type | Origin | Example |
|---|---|---|
| Inherent (Input) Error | Uncertainty in physical measurements or model parameters | Using or noisy sensor readings |
| Truncation Error | Approximating an infinite mathematical process by a finite number of steps | Stopping the Taylor series after a finite number of terms; replacing a derivative by a finite difference |
| Round-off Error | Finite word length (precision) of computers and calculators | Representing or in 32-bit / 64-bit floating-point format |
Accuracy, Precision, and Significant Digits
- Accuracy: How close a computed or measured value is to the true value.
- Precision: How closely repeated computations or measurements agree with each other (also refers to the number of significant digits retained).
- Significant Digits: Digits in a number that carry meaningful information about its reliability—all non-zero digits, zeros between non-zero digits, and trailing zeros after a decimal point.
- Scarborough Criterion (Significant-Digit Stopping Rule): An iterative result is guaranteed to be correct to at least significant digits if the approximate relative error satisfies:
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 .
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
- Choose two initial guesses and such that .
- Compute the midpoint of the current interval :
- Evaluate :
- If (or and ), is the root; stop.
- If , the root lies in , so set , .
- Otherwise (), the root lies in , so set , .
- 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
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:
- If , set .
- Otherwise, set .
- Pros: Always converges because the root remains bracketed; usually faster than bisection.
- Cons: If is strongly convex or concave on , one endpoint can stay fixed ("stagnant") for many iterations, reducing convergence to slow linear ().
Secant Method
Secant Method Formula
The secant method drops the bracketing requirement and always advances using the two most recent approximations and :
- Order of convergence: Superlinear, with order equal to the golden ratio:
- Advantages: Requires only one new function evaluation per iteration (once are known), does not require the derivative , and converges much faster than bisection or Regula Falsi.
- Drawbacks: Not guaranteed to converge if are far from the root, and fails if (division by zero).
| Aspect | Regula Falsi Method | Secant Method |
|---|---|---|
| Method Class | Bracketing (closed) method | Open-ended method |
| Sign Condition | Requires at every step | No opposite-sign requirement |
| Update Rule | Keeps the endpoint with opposite sign to | Always keeps the two latest iterates |
| Convergence | Guaranteed (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:
Newton–Raphson Iteration Formula
Starting from an initial guess , compute successively:
Convergence and Failure Cases
- Quadratic Convergence (): Near a simple root (where and ), the error satisfies:
Thus, the number of correct significant digits roughly doubles with every iteration.
- Pitfalls and Failure Modes:
- Zero or very small derivative (): Tangent is horizontal or nearly horizontal, shooting far away or causing division by zero.
- Oscillation / divergence near inflection points: Iterates may cycle endlessly or jump out of the domain (e.g., or for negative iterates).
- Multiple roots: If has multiplicity (), convergence slows from quadratic to linear.
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 .
Fixed-Point Iteration Scheme
Given an initial guess and iteration function , generate the sequence:
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 .
- Convergence behavior:
- If : monotonic convergence (staircase pattern).
- If : oscillatory convergence (cobweb/spiral pattern).
- If : divergence—choose a different algebraic rearrangement .
- Rate of convergence: Generally linear (), since . (In fact, Newton–Raphson is a special fixed-point iteration with , which satisfies at a simple root, explaining its quadratic convergence.)
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.
| Aspect | Bracketing Methods | Open-Ended Methods |
|---|---|---|
| Initial Requirement | Two guesses with | One guess (or two guesses for Secant), no sign check |
| Convergence Guarantee | Always converges for continuous | May diverge if initial guess is poor or |
| Speed | Slow (linear, ) | Fast when close to root (superlinear or quadratic ) |
| Even-Multiplicity Roots | Fails (no sign change across root) | Can locate multiple roots (though at reduced rate) |
| Method | Iteration Formula | Initial Guesses | Order of Convergence () | Function Evaluations / Step | Main 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:
- Jacobi-style update:
- Gauss–Seidel-style update (using the newly computed immediately):
1.7.2 Newton Raphson method
For the system and , first-order Taylor expansion about yields:
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
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: .
| Iteration | ||||
|---|---|---|---|---|
Calculating minimum iterations for :
With , , and :
Rounding up to the next integer gives iterations.
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 .
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 ).
The real root of is , which is correct to decimal places.
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 .)
After Newton–Raphson iterations, , converging to the exact root .
Exercises
Exercise — Solution of Non-Linear Equations
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:
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:
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 ():
After iterations of the secant method, the approximate root is (exact root ).
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 ():
After iterations of Regula Falsi, the approximate root is (with ).
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.
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.
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 :
After Newton–Raphson iterations, the solution is (rapidly approaching the exact solution ).