Understanding Fixed-Point Iteration Methods in Numerical Computing
Explore the concept of fixed-point iteration methods in numerical computing, including its application in finding roots and the construction of g(x) from f(x). Learn how to choose an appropriate g(x) function for convergence and understand the convergence criteria based on the derivative mean-value theorem.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Faculty of Engineering Mechanical Engineering Department MATH 2140 Numerical Methods Instructor: Dr. Mohamed El-Shazly Associate Prof. of Mechanical Design and Tribology melshazly@ksu.edu.sa Office: F072
B.1. Fixed Point Iteration Also known as one-point iteration or successive substitution To find the root for f(x) = 0, we reformulate f(x) = 0 so that there is an x on one side of the equation. x f = 0 ) ( If we can solve g(x) = x, we solve f(x) = 0. x is known as the fixed point of g(x). We solve g(x) = x by computing ) ( 1 x g x i i = + = ( ) g x x with given x 0 until xi+1 converges to x. 2
Fixed Point Iteration Example = + = x x x f 2 ( ) 2 3 0 2 3 x + = = = 2 2 2 3 0 2 3 x x x x x 2 2 i 3 x = = ( ) x g x + 1 i i 2 Reason: If x converges, i.e. xi+1 xi 2 i 2 i 3 3 x x = = x x + 1 i i 2 2 + = 2 i 2 3 0 x x i 3
Fixed Point Iteration There are infinite ways to construct g(x) from f(x). = = 2 (ans: x = 3 or -1) For example, ( ) 2 3 0 f x x x Case a: Case b: Case c: x = x = 2 2 x = 2 x 3 0 2 3 x 0 2 x x x x 2 x 3 0 x x = ( ) 2 3 0 = + 2 = 2 3 2 2 3 3 = + 2 3 x 2 = 3 x x = x = x 2 x 2 + ( ) 2 3 g x x 3 2 3 x = ( ) g x = ( ) g x 2 x 2 So which one is better? 4
Case a Case c Case b 3 2 i = + 3 x 2 3 x x = = x x + 1 i i + 1 i + 1 i 2 x 2 i x0 = 4 x1 = 3.31662 x2 = 3.10375 x3 = 3.03439 x4 = 3.01144 x5 = 3.00381 x0 = 4 x1 = 1.5 x2 = -6 x3 = -0.375 x4 = -1.263158 x5 = -0.919355 x6 = -1.02762 x7 = -0.990876 x8 = -1.00305 x0 = 4 x1 = 6.5 x2 = 19.625 x3 = 191.070 1. 2. 3. 4. 5. 6. 1. 2. 3. 4. 5. 6. 7. 8. 9. Converge, but slower 1. 2. 3. 4. Converge! Diverge! 5
How to choose g(x)? Can we know which g(x) would converge to solution before we do the computation? 6
Convergence of Fixed Point Iteration According to the derivative mean-value theorem, if g(x) and g'(x) are continuous over an interval xi x , there exists a value x = c within the interval such that ) ( ) ( ' c g have we (6), and (1) From i = ) ( ' ) 7 ( Thus 1 = = + ( ) g g x = ) 7 ( i x i = ( ) ( ) x and g g x + 1 i i i ) + ( ' 1 g c g c i i i i Therefore, if |g'(c)| < 1, the error decreases with each iteration. If |g'(c)| > 1, the error increase. If the derivative is positive, the iterative solution will be monotonic. If the derivative is negative, the errors will oscillate. 7
(a) |g'(x)| < 1, g'(x) is +ve converge, monotonic (b) |g'(x)| < 1, g'(x) is -ve converge, oscillate (c) |g'(x)| > 1, g'(x) is +ve diverge, monotonic (d) |g'(x)| > 1, g'(x) is -ve diverge, oscillate Demo Demo 8
