Multi-stage switching multiprocessor interconnecion

Multi-stage switching multiprocessor interconnecion

Fixed Point Method to find the root of the non-linear equation

Fixed Point Method [Linearly Convergent]

1.      Assign an initial value to x₀ and accuracy level E.

2.      Reform given equation as x = g(x)

3.      Compute x₁ = g(x₀).

4.      Check the required accuracy level of x₁.

If absolute value of (x₁ – x₀) / x₁ < E then

Write x₁ as the root of the equation and go to 4.

Otherwise

            Set x₀ = x₁ and

            Go to step 2

5.      Stop

The equation x_i+1 = g (x_i) where I = 0, 1, 2 … is called the fixed point iteration formula.

Example: Find the square root of 5 using the equation x² - 5 = 0 by using fixed point iteration method.

Solⁿ: Here f(x) = x² – 5

Step 1: Assigning Initial value of x₀ = 1 and E = 0.01

Step 2: Reforming the equation x² - 5 = 0

            Or x² = 5

            Or x = 5/x

            Or 2x = 5/x + x [Adding x in both sides]

             x = [5/x + x] / 2

Step 3: Iteration I:

Computing x₁ = g(x₀).

                        x₁=[5/x₀ + x₀] / 2 = 3  [x_{0 = 1}]

Step 4: Checking accuracy level,          

            Absolute value of (x₁ – x₀) / x₁ < E

            (3 - 1) / 3 = 0.6667

            0.6667 < 0.01 which is false

            So, set x₀ = x₁ and go to step 3

            Iteration II:

            Computing x₁ = g(x₀).

                        x₁=[5/x₀ + x₀] / 2 = …

Repeat the iterations until error criteria satisfied.

If error criteria is satisfied then,

Write improved estimation x₁ as the root of the equation and stop.

Secant Method to find the root of the non-linear equation

Secant Method [Super-linear convergence]

1.      Decide two initial points x₁ and x₂, and accuracy level E.

2.      Compute f(x₁) and f(x₂)

3.      Compute improved value x₃ with the help of x₁ an x₂,

i.e. x₃ = x₂ - ( ( f(x₂) (x₂-x₁) ) / ( f(x₂) - f(x₁) ) )

4.      Checking the accuracy level of improved estimation i.e. x₃.

If absolute value of (x₃ – x₂) / x₃ < E

            Write improved estimation or x₃ as the root of the equation and go to 5.

Otherwise

            Set x₁ = x₂ and f(x₁) = f(x₂)

            Set x₂ = x₃ and f(x₂) = f(x₃)

            Go to step 3

5.      Stop

Example: Use the secant method to estimate the root of the equation x²-4x-10 = 0 with the initial estimates of x₁ = 4 and x₂ = 2.

Solⁿ: Given f(x) = x2-4x-10 = 0

Step 1: Initial points x₁ = 4 and x₂ = 2, and Accuracy level E = 0.01

Step 2: Computing f(x₁) and f(x₂),

            f(x₁) = 4²- 4*4 – 10 = -10

            f(x₂) = 2² – 4*2 – 10 = -14

Step 3: Iteration I:

Computing improves root x3,

            x₃ = x₂ - ( ( f(x₂) (x₂-x₁) ) / ( f(x₂) - f(x₁) ) ) = 2 - ( ( ( -14 ) ( 2 – 4 ) ) / ( ( -14 ) - ( -10 ) ) )

                = 2-(28 / (-4)) = 9               

Step 4: Checking accuracy level,

Absolute value of (x₃ – x₂) / x₃ < E

(x₃ – x₂) / x₃ = (9-2) / 9 = 7/9 = 0.7778

Here 0.7778 < 0.01 is false

Error criteria are not satisfied.

So,       Set x₁ = x₂ = 2 and f(x₁) = f(x₂) = -14

Set x₂ = x₃ = 9 and f(x₂) = f(x₃) = f(9) = 9² - 4*9 – 10 = 35

            Go to step 3

Iteration II: Calculating improved estimation of x_3, using

x₃ = x₂ - ( ( f(x₂) (x₂-x₁) ) / ( f(x₂) - f(x₁) ) ) = …

Repeat the iterations until error criteria satisfied.

If error criteria is satisfied then,

Write improved estimation x₃ as the root of the equation and stop.

Newton-Raphson Method to find the root of the non-linear equation

Newton-Raphson Algorithm [Quadratic convergence]
  

1.      Assign an initial value to x; say x₀ and accuracy level E.

2.      Calculate the f(x₀) and f'(x₀) [f'(x₀) is derivative of f(x₀)].

3.      Find the improved estimate of x₀.

x₁ = x₀ - ( f(x₀) / f'(x₀) )

4.      Check the accuracy level of the improved estimation.

If absolute value of (x₁ - x₀) / x₁ < E

            Write improved estimation as the root of the equation and stop.

Otherwise

            Continue.

5.      Set x₀ = x₁ and repeat steps 3.

Example: Find the root of the equation x²-4x-10 = 0, using Newton-Raphson method.

Solⁿ: Here given, f(x) = x²-4x-10.

Step 1: Since initial value of x is not provided so we can assume any value as initial value for x. say x = 0, i.e. x₀ = 0.

And accuracy level E = 0.01.      

Step 2: Computing f(x₀) and f'(x₀)

            Here f(x) = x²-4x-10 and f'(x) = 2x – 4

            So, f(x₀) = f(0) = 0² - 4*0 – 10 = -10

            And f'(x₀) = 2*0 – 4 = -4

Step 3: Iteration I:

Calculating improved estimation of x_0, using

  x₁ = x₀ - ( f(x₀) / f'(x₀) ) = 0 – ( -10 / -4 ) = -2.5

Step 4: Checking the accuracy level of improved estimation using,

 Absolute value of (x₁ - x₀) / x₁ < E

(x₁ - x₀) / x₁ = (-2.5 – 0) / -2.5 = 1.

Or 1 < 0.01 [Which is false.]

Error criteria not satisfied.

Step 5: Set x₀ = x₁ and go to step 3.

Iteration II: Calculating improved estimation of x_0, using

            x₁ = x₀ - ( f(x₀) / f'(x₀) ) = …

Repeat the iterations until error criteria satisfied.

If error criteria is satisfied then,

Write improved estimation as the root of the equation and stop.

Limitations of Newton-Raphson Method

1.      Division by zero may occur if f'(x_i) is zero or very close to zero

2.      If the initial assumption is too far away from the required root, the process may converge to some other root.

3.      A particular value in the iteration sequence may repeat, resulting in an infinite loop. This occurs when the tangent to the curve f(x) at x = x_i+1 cuts the x-axis again at x = x_i.