Algorithm

Halley's 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:	Find `f(x_0)`, `f'(x_0)` and `f''(x_0)` `x_1=x_0-(2*f(x_0)*f'(x_0))/(2*f'(x_0)^2-f(x_0)*f''(x_0))`
Step-4:	If `f(x_1) = 0` then `x_1` is an exact root, else `x_0 = x_1`
Step-5:	Repeat steps 2 to 4 until `f(x_i) = 0` or `|f(x_i)| <= "Accuracy"`

---

Example-1
1. Find a root of an equation `f(x)=x^3-x-1` using Halley's method

Solution:
Here `x^3-x-1=0`

Let `f(x) = x^3-x-1`

`d/(dx)(x^3-x-1)=3x^2-1`

`d/(dx)(x^3-x-1)`

`=d/(dx)(x^3)-d/(dx)(x)-d/(dx)(1)`

`=3x^2-1-0`

`=3x^2-1`

`d/(dx)(3x^2-1)=6x`

`d/(dx)(3x^2-1)`

`=d/(dx)(3x^2)-d/(dx)(1)`

`=6x-0`

`=6x`

`:. f'(x) = 3x^2-1`

`:. f ''(x) = 6x`

Here

`x`	0	1	2
`f(x)`	-1	-1	5

Here `f(1) = -1 < 0 and f(2) = 5 > 0`

`:.` Root lies between `1` and `2`

`x_0 = (1 + 2)/2 = 1.5`

`x_0 = 1.5`


`1^(st)` iteration :

`f(x_0)=f(1.5)=1.5^3-1.5-1=0.875`

`f'(x_0)=f'(1.5)=3*1.5^2-1=5.75`

`f''(x_0)=f'(1.5)=6*1.5=9`

`x_1=x_0-(2*f(x_0)*f'(x_0))/(2*f'(x_0)^2-f(x_0)*f''(x_0))`

`x_1=1.5-(2xx0.875xx5.75)/(2xx(5.75)^2-(5.75)xx(9))`

`x_1=1.3273`


`2^(nd)` iteration :

`f(x_1)=f(1.3273)=1.3273^3-1.3273-1=0.0108`

`f'(x_1)=f'(1.3273)=3*1.3273^2-1=4.2848`

`f''(x_1)=f'(1.3273)=6*1.3273=7.9635`

`x_2=x_1-(2*f(x_1)*f'(x_1))/(2*f'(x_1)^2-f(x_1)*f''(x_1))`

`x_2=1.3273-(2xx0.0108xx4.2848)/(2xx(4.2848)^2-(4.2848)xx(7.9635))`

`x_2=1.3247`


`3^(rd)` iteration :

`f(x_2)=f(1.3247)=1.3247^3-1.3247-1=0`

`f'(x_2)=f'(1.3247)=3*1.3247^2-1=4.2646`

`f''(x_2)=f'(1.3247)=6*1.3247=7.9483`

`x_3=x_2-(2*f(x_2)*f'(x_2))/(2*f'(x_2)^2-f(x_2)*f''(x_2))`

`x_3=1.3247-(2xx0xx4.2646)/(2xx(4.2646)^2-(4.2646)xx(7.9483))`

`x_3=1.3247`


Approximate root of the equation `x^3-x-1=0` using Halleys method is `1.3247` (After 3 iterations)

`n`	`x_0`	`f(x_0)`	`f'(x_0)`	`f''(x_0)`	`x_1`	Update
1	1.5	0.875	5.75	9	1.3273	`x_0 = x_1`
2	1.3273	0.0108	4.2848	7.9635	1.3247	`x_0 = x_1`
3	1.3247	0	4.2646	7.9483	1.3247	`x_0 = x_1`

---

---