0% found this document useful (0 votes)
32 views7 pages

Numerical Methods for Root Finding

The document discusses numerical methods for finding roots of functions, emphasizing the importance of continuity and sign changes. It outlines three methods: Interval Bisection, Linear Interpolation, and the Newton-Raphson Method, detailing their processes and considerations for accuracy. Key points include the necessity of careful initial point selection in Newton's Method to ensure convergence and the importance of using exact values in calculations.

Uploaded by

mervinlo
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
32 views7 pages

Numerical Methods for Root Finding

The document discusses numerical methods for finding roots of functions, emphasizing the importance of continuity and sign changes. It outlines three methods: Interval Bisection, Linear Interpolation, and the Newton-Raphson Method, detailing their processes and considerations for accuracy. Key points include the necessity of careful initial point selection in Newton's Method to ensure convergence and the importance of using exact values in calculations.

Uploaded by

mervinlo
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Numerical Methods

Numerical Methods to solve f(x) = 0

Basic Concept: Sign Diagram and Locating Roots

If :

1) f(x) is continuous on the interval [a, b]


2) f(a) and f(b) have opposite sign

Then:

1) F(x) has at least 1 root, for a < x < b

Note logical fallacies:

1) At least 1 root doesn’t mean exactly 1 root


2) No sign change doesn’t imply no root
3) Functions with vertical asymptote has sign change but not continuous
Numerical Method 1: Interval Bisection

1) f(a) and f(b) have opposite sign on the interval [a, b]


2) take the mid-point (a+b) / 2 as the 1st solution approximation, then repeat the process until
required degree of accuracy is achieved.

Example:
Example

Numerical Method 2: Linear Interpolation

1) Draw a straight line between the points (a, f(a)) and (b, f(b))
2) The x-intercept is the 1st approximation 𝑥1
3) Use similar triangle properties and ratios to estimate 𝑥1 , and find 𝑓(𝑥1)
4) Replace the end with same sign as 𝑓(𝑥1), then repeat the process until required degree of
accuracy is achieved.

Example:
Example:

Numerical Method 3: The Newton-Raphson Method (Newton’s Method)

The Newton-Raphson Formula is:

𝑓(𝑥𝑛 )
𝑥𝑛+1 = 𝑥𝑛 −
𝑓 ′(𝑥𝑛 )

1) The method uses tangent line to find increasing accurate approximation of x.


2) 𝑥𝑛+1 is the point at which the tangent line at 𝑥𝑛 intersects x-axis.
3) If 𝑥0 is chosen carefully, it will converge quickly
4) If 𝑥0 is not chosen carefully, it might converge slowly, or even fail.
Example: if the initial point is close to turning point, ie the derivative is close to 0, the tangent will
intercept x-axis far away from the initial point.

Example: if at any point it is a turning point, then the method with fail because the derivative = 0. I.e.
the tangent is a horizontal line and will never intersect with x-axis.
Example:

Final Note: Don’t use approximated value in each iteration. Use exact value and use calculator
memory function to store exact values.

Common questions

Powered by AI

Linear interpolation would be inappropriate in scenarios where the function between two points exhibits significant non-linearity or curvature. As linear interpolation assumes linearity between two points, using it on such functions may result in large errors and poor approximations of the root. Furthermore, if the points (a, b) do not have a change of sign, then linear interpolation cannot be correctly applied to determine the root, as the assumption of crossing the x-axis becomes invalid .

A continuous function f(x) on an interval [a, b] will have at least one root between a and b if two conditions are met: 1) f(x) is continuous on [a, b], and 2) f(a) and f(b) have opposite signs. This is due to the Intermediate Value Theorem, which states that if a continuous function changes sign over an interval, there must be at least one root within that interval .

Using an approximated value instead of an exact one in iterative numerical methods can introduce significant errors due to cumulative error propagation. Each iteration builds upon the previous results; hence, starting with approximated values may magnify these initial inaccuracies through each subsequent step. This can lead to convergence on an incorrect value or slow down the convergence due to amplified errors. Therefore, using exact values stored in calculator memory or provided by a computational algorithm ensures higher precision and accuracy throughout the iterative process .

The statement "No sign change doesn’t imply no root" suggests that a continuous function may have roots even if the values at endpoints of an interval do not show a sign change. This situation can especially arise in functions that are not monotonic or have local extremums within the interval, allowing them to touch the x-axis without crossing it across the interval boundaries. Such scenarios indicate the limitation of sign analysis for root detection and highlight the need for comprehensive scanning or modern algorithmic techniques for root identification in numerical analysis, beyond simple sign testing .

The Newton-Raphson Method offers numerous advantages over other numerical methods when its conditions are suitably met. One key advantage is its rapid convergence, often showing quadratic convergence, meaning the error decreases exponentially at each step, unlike the linear convergence of methods like Interval Bisection. This efficiency means fewer iterations are needed to achieve high precision. However, this rapid convergence relies on an adequately chosen initial guess and the absence of problematic conditions such as a derivative near zero at the guess point .

The Newton-Raphson Method can encounter issues if the initial guess 𝑥0 is not chosen carefully. If 𝑥0 is close to a turning point where the derivative of the function, 𝑓'(𝑥0), is close to 0, the method may converge slowly or fail altogether, as the tangent line will intersect the x-axis far away from the initial point. Additionally, if the derivative at the guess is exactly 0, the method will fail because the tangent will be horizontal and never intersect the x-axis. These pitfalls necessitate careful selection of initial guesses and may require verification through other methods to ensure convergence .

The initial value (𝑥0) is critical in determining the performance of the Newton-Raphson Method. Its primary role is as the starting point in the iterative approach where the tangent line is applied to find successively better approximations of the root. Selecting an optimal 𝑥0 is crucial; it should be close enough to the actual root to enable rapid convergence and avoid regions where the function's derivative is zero or near zero, which would severely affect performance. To select such a value, preliminary analysis or weaker but wider-range methods like Interval Bisection could be leveraged to narrow down promising initial points .

In the Newton-Raphson Method, a tangent line to the function at a specific point 𝑥𝑛 is used to find the roots. The method uses the derivative of the function to construct this tangent, which approximates the behavior of the function near 𝑥𝑛. The x-intercept of this tangent line is then used as the next approximation point, 𝑥𝑛+1. As the process repeats, the tangent lines provide increasingly accurate approximations of the function's root, under the condition that the initial guess is sufficiently close to the actual root .

A sign change of a function on an interval indicates at least one root due to the Intermediate Value Theorem, but it does not guarantee a unique root. There could be multiple roots close to each other making the function oscillate, thus causing a sign change over small segments within the interval. Additionally, a function could have a sign change in separate intervals, further suggesting multiple roots. Without additional information or analysis, a single sign change does not imply exactly one root .

The Interval Bisection method functions by taking an interval [a, b] where the function f(x) changes signs (i.e., f(a) and f(b) have opposite signs), indicating a root lies within. The midpoint of the interval, (a+b)/2, is calculated and evaluated. Depending on the sign of f at the midpoint, one half of the interval is discarded, and the process is repeated until a satisfactory approximation is achieved. It is slower compared to other methods because it halts the potential of exponential convergence seen in methods like Newton-Raphson, as it only guarantees linear convergence by systematically halving the interval size .

You might also like