# Name: Sujit Kadam

## Project Report: Fixed point iteration

### Introduction

My final project is about Fixed point iteration. I got interested to Fixed point iteration when I learnt about Babylonian method. It’s a very old process but still used today and is powerful at the same time. I was amazed to know its application in Newton Raphson’s method and Secant method. I wanted to learn more about this iteration process. Hence, I opted for this process. This project is intended to get some more knowledge about Fixed point iteration and its application. The project explains about the different concepts and applications of Fixed point iteration using examples, exercises and quizzes.

### Initial Experience

After reading wiki page of Fixed Point Iteration, I felt something’s missing. I started to think and search various explanations on Fixed point iteration. I read few books online. I found that many things can be added to improve Fixed point iteration on Wikipedia. After some initial research on topic I decided to write my project proposal that described about the things I will be adding. In fact, initially I was a little bit confused about Instructor's expectations. I thought that I need to add whatever I have learned and some extra information on Fixed point iteration. Accordingly, I made my project proposal.

### I proposed to add points mentioned below

1. Introductory definition and explanation about the iteration: Introduction, definition, formula and explanation about Fixed point iteration.
2. Supporting theorems and derivations: Banach fixed point theorem, Babylonian method and any other important derivation.
3. Rate of convergence: Proof and explain convergence speed of the iteration method.
4. Examples to explain fixed point iteration: Some exercises on fixed point iteration based on different scenarios.
5. Applications and usefulness of the iteration: Explain application of the iteration in Newton’s method and Secant method.
6. Disadvantages or failure of this iteration: Explore and explain any cases of failure of this iteration method.
7. Exercises and quizzes on fixed point iteration: Few exercises based on fixed point iteration.
8. Important links and external study help materials: If I find any important interesting link related to the topic then I will post it in the project.

### Instructor's input

My instructor pointed out that it would be much better if I don’t duplicate material and add something to the topic that is not present in Wikipedia or any online resources. The explanation of Fixed point iteration, derivation and theorems are already explained in Wikipedia pages are pretty good enough to understand. Instructor also pointed out that I should concentrate more on examples, exercises and quizzes. The examples should clear some basic and new concepts. Exercises should help readers to apply the concepts. Quizzes should test readers’ concept on Fixed point iteration. Instructor's comment were really helpful for me to know which points exactly I need to concentrate. It really add some good new information to the content.

### Main Project

#### Motivation

After thinking about the inputs from the instructor, I started some in-depth research on Fixed point iteration material. I checked out some books and online material and found that Wikipedia is missing on some parts in Fixed point iteration section. I thought to add algorithm of Fixed point iteration, a new concept related to derivative of function and example that can be used in application of Fixed point iteration i.e. Newton Raphson’s method, difficult exercises and quizzes. In our Numerical analysis course we studied many methods and iterations to find root. But I think Fixed point iteration is really a powerful yet simple tool because of which it was used new methods. It's accuracy is good, convergence rate is linear to quadratic (in some cases) and chances of failure is less compared to other methods. It offers really a good deal.

#### Proposed changes

1. Introductory definition and explanation about the iteration: Introduction, definition, formula and explanation about Fixed point iteration.
2. Supporting theorems and derivations: Banach fixed point theorem, Babylonian method and any other important derivation.
3. Rate of convergence: Proof and explain convergence speed of the iteration method.
4. Examples to explain fixed point iteration: Some exercises on fixed point iteration based on different scenarios.
5. Applications and usefulness of the iteration: Explain application of the iteration in Newton’s method and Secant method.
6. Disadvantages or failure of this iteration: Explore and explain any cases of failure of this iteration method.
7. Exercises and quizzes on fixed point iteration: Few exercises based on fixed point iteration.
8. Important links and external study help materials: If I find any important interesting link related to the topic then I will post it in the project.

#### Actual changes

1. Added Algorithm for Fixed point iteration that was not included in Wikipedia.
2. Added a simple example that finds the square root of 2 correct till 3 decimal places.
3. Added an example that proves a new concept not mentioned in Wikipedia: If |g'(x)| > 1 then sequence will not converge to desired value. If |g'(x)| < 1 then sequence will converge to desired value. This concept can be used in Newton Raphson method.
4. Mentioned about the applications of Fixed point iteration: Newton Raphson’s method and Secant method.
5. Added exercise that calculates the square root of 0.5 correct till 3 decimal places. The reason to choose this problem was to show that if a square root of a number near to zero is chosen then by using Babylonian method it first diverges and then converges to the desired value. The exercise displays the iteration steps.
6. Added quizzes based on the concepts of Fixed point iteration.

#### Conclusion

Concluding, my project work I found that there are still many concepts to be learned in Fixed point iteration. I have tried to cover some concepts but there are still some concepts yet to be touched and learned. Its concepts are used in Newton Raphson and Secant method. Fixed point iteration is really an effective way of finding square root.

#### References

1. Burden, Richard L., and J. Douglas. Faires. Numerical Analysis. Belmont, CA: Thomson Brooks/Cole, 2005. Electronic.
2. Answers.com - Fixed Point Iteration Methods plus Algorithm." WikiAnswers - The Q&A Wiki. Web. 07 Nov. 2010. <http://wiki.answers.com/Q/Fixed_point_iteration_methods_plus_algorithm>.

## Exercise Template

Simple Exercise: What is 10*10?

## Quiz template

1

If x + 3x = -8, then x + 1 =

 -2 -1 1 2

2

 The determinant of ${\displaystyle \left[{\begin{array}{c c}6&8\\5&4\end{array}}\right]}$ is .

3

 ${\displaystyle \displaystyle \ y_{1}=}$ ${\displaystyle \displaystyle \ y_{2}=}$ ${\displaystyle \displaystyle \ y_{3}=}$ Next, we have Ux = y ${\displaystyle {\begin{bmatrix}1&10&-6\\0&5&-10\\0&0&19\end{bmatrix}}}$ X ${\displaystyle {\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\end{bmatrix}}}$ = ${\displaystyle {\begin{bmatrix}y_{1}\\y_{2}\\y_{3}\end{bmatrix}}}$ Use backward substitution we have: ${\displaystyle \displaystyle \ x_{1}=}$ ${\displaystyle \displaystyle \ x_{2}=}$ ${\displaystyle \displaystyle \ x_{3}=}$

## Numerical Analysis

Topic Proposal: Fixed point iteration

I would like to propose to write on “Fixed point” iteration topic in Numerical analysis as my project. The goal of the project is to provide complete information about Fixed Point iteration on one single platform. I will be giving an introduction on Fixed point iteration with explanation. The project will first explain in detail about Fixed point iteration and its definition. Once the reader understands the definition then the project moves towards any supporting theorems or derivations of the formulas used in Fixed point iteration. Rate of convergence of the method will be explained to explain the speed of the method. The iteration will be illustrated by different examples to provide in-depth knowledge of the topic. At least two examples will be illustrated to explain the topic. The applications and usefulness of the iteration will be explained. I will also try to find examples or cases where fixed point may fail to converge to find square roots. At the end, the project will wrap asking some questions, exercises, quizzes and important links for external study.

List of topics I am planning to cover in my project:

1. Introductory definition and explanation about the iteration: Introduction, definition, formula and explanation about Fixed point iteration.
2. Supporting theorems and derivations: Banach fixed point theorem, Babylonian method and any other important derivation.
3. Rate of convergence: Proof and explain convergence speed of the iteration method.
4. Examples to explain fixed point iteration: Some exercises on fixed point iteration based on different scenarios.
5. Applications and usefulness of the iteration: Explain application of the iteration in Newton’s method and Secant method.
6. Disadvantages or failure of this iteration: Explore and explain any cases of failure of this iteration method.
7. Exercises and quizzes on fixed point iteration: Few exercises based on fixed point iteration.
8. Important links and external study help materials: If I find any important interesting link related to the topic then I will post it in the project.

## Project Presentation

### Fixed Point Iteration

#### Algorithm

To find a solution to p = g(p) given an initial approximation p0.

INPUT: Initial approximation p0; tolerance TOL; maximum number of iterations N0. OUTPUT: approximate solution p or message of failure.

Step 1: Set i =1

Step 2: While ${\displaystyle i\leq No}$ Steps 3 - 6

Step 3: Set p = g(p0)

Step 4: If ${\displaystyle |p-po|\leq TOL}$ then OUTPUT (p); (The procedure was successful). STOP.

Step 5: Set i = i + 1

Step 6: Set p0 = p. (Update p0)

Step 7: OUTPUT ('The method failed after N0 iterations'). STOP.

#### Examples

1. Find square root of 2 accurate till third decimal (10-3). The initial point is 2 .

We know that,
x0 = 2
xn+1 = 0.5 * ( x0 + (2/ x0))
x1 = 0.5 * (2 + (2/2)) = 1.5
x2 = 0.5 * (1.5 + (2/1.5)) = 1.416
x3 = 0.5 * (1.416 + (2/1.416)) = 1.4142
We found out the square root of 2 accurate till 4th decimal in 3 steps.

2. Consider the iteration pn+1 = g(p0) when the function g(x) = 1 + x - x2/4 is used. The fixed points can be found by solving equations x = g(x). The two solutions (fixed points of g) are x = -2 and x = 2. The derivative of the function is g'(x) = 1 - x/2, and there are only two cases to consider

Case 1 (P = -2):
We get
P1 = -2.100625
P2 = -2.20378135
..... ${\displaystyle \infty }$
Therefore, if |g'(x)| > 1 then sequence will not converge to P = -2
Case 2 (P = 2):
We get
P1 = 1.96
P2 = 1.9996
..... 2
Therefore, if |g'(x)| < 1 then sequence will converge to P = 2

#### Applications

Two methods in which Fixed point technique is used:

1. Newton Raphson Method

Formula
${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}}$
where,
xn - initial point
f(xn) is the value of the function at that point
f'(xn) is the value of the differentiated function at that point.
Plug all these values into the above equation to get xn+1. It becomes the next initial point. Repeat until you get a point within an acceptable degree of error

2. Secant Method

Used to avoid differentiated form in Newton Raphson's method. Only problem is you need two initial points for this method (xn and xn-1)
Formula
${\displaystyle x_{n}=x_{n-1}-f(x_{n-1}){\frac {x_{n-1}-x_{n-2}}{f(x_{n-1})-f(x_{n-2})}}}$
Similar to Newton Raphson's method plug in all values to generate next approximation.

#### Exercises

If 'f' is continuous and 'x' is a fixed point on 'f' then what is 'f(x)'?

Find the square root of 0.5 using fixed point iteration? Initial point 0.1 and tolerance 10-3

Calculating x1 i.e. 1st Iteration

Calculating x2 i.e. 2nd Iteration

Calculating x3 i.e. 3rd Iteration

Calculating x4 i.e. 4th Iteration

Calculating x5 i.e. 5th Iteration

In above problem, how many iterations or steps are needed to achieve an accuracy of 10-8

#### Quizzes

<quiz display=simple> {Is there any possibility that the fixed point isn't unique |type="()"} -Yes +No

{ Assuming g ε C[a,b], If the range of the mapping y = g(x) satisfies y ε [a,b], then} +g has a fixed point in [a,b] -g has no fixed point in [a,b] -Depends on some other condition

{ If |g'(x)| > 1, then the iteration xn+1 = g (x) produces a sequence } +that diverges away from P -that converges towards P -Depends

{The fixed point iteration will diverge unless x0 = 0. |type="()"} +True -False

{Consider the following fixed point iteration; ${\displaystyle f(x)={\frac {1}{2}}\left({\frac {a}{x}}+x\right)}$. Rate (order) of convergence of this iteration is |type="()"} +Quadratic -Linear -Cubic