1. Algorithm & Example-1 `f(x)=x^3-x-1`
Algorithm
|
Bisection method Steps (Rule)
|
|
Step-1:
|
Find points `a` and `b` such that `a < b` and `f(a) * f(b) < 0`.
|
|
Step-2:
|
Take the interval `[a, b]` and
find next value `x_0 = (a+b)/2`
|
|
Step-3:
|
If `f(x_0) = 0` then `x_0` is an exact root,
else if `f(a) * f(x_0) < 0` then `b = x_0`,
else if `f(x_0) * f(b) < 0` then `a = x_0`.
|
|
Step-4:
|
Repeat steps 2 & 3 until `f(x_i) = 0` or `|f(x_i)| <= "Accuracy"`
|
Example-1
Find a root of an equation `f(x)=x^3-x-1` using Bisection method
Solution:
Here `x^3-x-1=0`
Let `f(x) = x^3-x-1`
Here
`1^(st)` iteration :
Here `f(1) = -1 < 0` and `f(2) = 5 > 0`
`:.` Now, Root lies between `1` and `2`
`x_0 = (1 + 2)/2 = 1.5`
`f(x_0) = f(1.5) = 0.875 > 0`
`2^(nd)` iteration :
Here `f(1) = -1 < 0` and `f(1.5) = 0.875 > 0`
`:.` Now, Root lies between `1` and `1.5`
`x_1 = (1 + 1.5)/2 = 1.25`
`f(x_1) = f(1.25) = -0.29688 < 0`
`3^(rd)` iteration :
Here `f(1.25) = -0.29688 < 0` and `f(1.5) = 0.875 > 0`
`:.` Now, Root lies between `1.25` and `1.5`
`x_2 = (1.25 + 1.5)/2 = 1.375`
`f(x_2) = f(1.375) = 0.22461 > 0`
`4^(th)` iteration :
Here `f(1.25) = -0.29688 < 0` and `f(1.375) = 0.22461 > 0`
`:.` Now, Root lies between `1.25` and `1.375`
`x_3 = (1.25 + 1.375)/2 = 1.3125`
`f(x_3) = f(1.3125) = -0.05151 < 0`
`5^(th)` iteration :
Here `f(1.3125) = -0.05151 < 0` and `f(1.375) = 0.22461 > 0`
`:.` Now, Root lies between `1.3125` and `1.375`
`x_4 = (1.3125 + 1.375)/2 = 1.34375`
`f(x_4) = f(1.34375) = 0.08261 > 0`
`6^(th)` iteration :
Here `f(1.3125) = -0.05151 < 0` and `f(1.34375) = 0.08261 > 0`
`:.` Now, Root lies between `1.3125` and `1.34375`
`x_5 = (1.3125 + 1.34375)/2 = 1.32812`
`f(x_5) = f(1.32812) = 0.01458 > 0`
`7^(th)` iteration :
Here `f(1.3125) = -0.05151 < 0` and `f(1.32812) = 0.01458 > 0`
`:.` Now, Root lies between `1.3125` and `1.32812`
`x_6 = (1.3125 + 1.32812)/2 = 1.32031`
`f(x_6) = f(1.32031) = -0.01871 < 0`
`8^(th)` iteration :
Here `f(1.32031) = -0.01871 < 0` and `f(1.32812) = 0.01458 > 0`
`:.` Now, Root lies between `1.32031` and `1.32812`
`x_7 = (1.32031 + 1.32812)/2 = 1.32422`
`f(x_7) = f(1.32422) = -0.00213 < 0`
`9^(th)` iteration :
Here `f(1.32422) = -0.00213 < 0` and `f(1.32812) = 0.01458 > 0`
`:.` Now, Root lies between `1.32422` and `1.32812`
`x_8 = (1.32422 + 1.32812)/2 = 1.32617`
`f(x_8) = f(1.32617) = 0.00621 > 0`
`10^(th)` iteration :
Here `f(1.32422) = -0.00213 < 0` and `f(1.32617) = 0.00621 > 0`
`:.` Now, Root lies between `1.32422` and `1.32617`
`x_9 = (1.32422 + 1.32617)/2 = 1.3252`
`f(x_9) = f(1.3252) = 0.00204 > 0`
`11^(th)` iteration :
Here `f(1.32422) = -0.00213 < 0` and `f(1.3252) = 0.00204 > 0`
`:.` Now, Root lies between `1.32422` and `1.3252`
`x_10 = (1.32422 + 1.3252)/2 = 1.32471`
`f(x_10) = f(1.32471) = -0.00005 < 0`
Approximate root of the equation `x^3-x-1=0` using Bisection method is `1.32471`
| `n` | `a` | `f(a)` | `b` | `f(b)` | `c=(a + b)/2` | `f(c)` | Update | | 1 | 1 | -1 | 2 | 5 | 1.5 | 0.875 | `b = c` | | 2 | 1 | -1 | 1.5 | 0.875 | 1.25 | -0.29688 | `a = c` | | 3 | 1.25 | -0.29688 | 1.5 | 0.875 | 1.375 | 0.22461 | `b = c` | | 4 | 1.25 | -0.29688 | 1.375 | 0.22461 | 1.3125 | -0.05151 | `a = c` | | 5 | 1.3125 | -0.05151 | 1.375 | 0.22461 | 1.34375 | 0.08261 | `b = c` | | 6 | 1.3125 | -0.05151 | 1.34375 | 0.08261 | 1.32812 | 0.01458 | `b = c` | | 7 | 1.3125 | -0.05151 | 1.32812 | 0.01458 | 1.32031 | -0.01871 | `a = c` | | 8 | 1.32031 | -0.01871 | 1.32812 | 0.01458 | 1.32422 | -0.00213 | `a = c` | | 9 | 1.32422 | -0.00213 | 1.32812 | 0.01458 | 1.32617 | 0.00621 | `b = c` | | 10 | 1.32422 | -0.00213 | 1.32617 | 0.00621 | 1.3252 | 0.00204 | `b = c` | | 11 | 1.32422 | -0.00213 | 1.3252 | 0.00204 | 1.32471 | -0.00005 | `a = c` |
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
|
