Jump to content

User:Gauge00/Householder

From Wikipedia, the free encyclopedia

Another derivation using mathematical induction

derivatives of the

[edit]

Let's define a new function . Then

By defferentiating

, that is,

Differentiating multiple times, we get

The coefficients of the above equations are those of the Pascal's triangle. Taking notation for the binomial coefficient, we would get

Though some of followings would not be used at the derivation, let's expand some of above equations to see what forms they have,

...

Therefore


Relation with

[edit]

By the Taylor expansion, we get (assuming )

where, is the initial guess of the root of .

Let approximate f(x) by dropping higher orders of the right hand side;


Then f(x) is approximated to a linear function, and now let's denote is the point where met axis,

This is the Newton's method.


Let's define

Let's call above as or

Therefore the Newton's method is the first kind of Householder's method.


Now by taking three therms of the original Taylor series,



Therefore



and by substituting the of the right hand side by , we get


This is the Halley's method. And Let's call as or



Therefore the Halley's method is the second kind of Householder's method.

As we progress, we get

This is the third kind of Householder's method.


Now



Derivation

[edit]

Following is not Gauge00's derivation, it is from the original derivation Householder's method.

An exact derivation of the Householder's methods starts from the Padé approximation of order (d+1), where the approximant with linear numerator of the form is chosen.

The Padé approximation has the form

where is the initial guess, and 's and are constants that are dependent on and .

Since , will be used as the second guess,

In Pade approximant, the degrees of numerator and denominator polynomials have to add to the order of the approximant. Therefore, in our approximation of order, has to hold.

One could determine the Padé approximant starting from the Taylor polynomial of f using Euclid's algorithm.

However, starting from the Taylor polynomial of 1/f is shorter and leads directly to the given formula.



And , let's calculate

This has to be the denominator of the Pade approximant of f(x) of d th order of , and has to hold

.

Now, solving the last equation ,


This implies the iteration formula

.