Durand–Kerner method: Difference between revisions

Revision as of 14:58, 3 November 2020

Revision as of 15:04, 3 November 2020

Line 8:

This explanation considers equations of [[Degree of a polynomial|degree]] four. It is easily generalized to other degrees.

Let the polynomial ƒ''f'' be defined by

: <math>f(x) = x^4 + ax^3 + bx^2 + cx + d.</math>

for all ''x''.

The known numbers ''a'', ''b'', ''c'', ''d'' are the [[coefficient]]s.

Let the (complex) numbers ''P'', ''Q'', ''R'', ''S'' be the roots of this polynomial &fnof;''f''.

Then

: <math>f(x) = (x - P)(x - Q)(x - R)(x - S)</math>

for all ''x''. One can isolate the value ''P'' from this equation,:

: <math>P = x - \frac{f(x)}{(x - Q)(x - R)(x - S)}.</math>

So if used as a [[fixed point (mathematics)|fixed -point]] [[iteration]]

: <math>x_1 := x_0 - \frac{f(x_0)}{(x_0 - Q)(x_0 - R)(x_0 - S)},</math>

it is strongly stable in that every initial point ''x''₀'' ≠ ''Q'', ''R'', ''S''

delivers after one iteration the root ''P'' = ''x''₁''.

Furthermore, if one replaces the zeros ''Q'', ''R'' and ''S''

by approximations ''q'' ≈ ''Q'', ''r'' ≈ ''R'', ''s'' ≈ ''S'',

such that ''q'', ''r'', ''s'' are not equal to ''P'', then ''P''

is still a fixed point of the perturbed fixed -point iteration

: <math>x_{k+1} := x_k - \frac{f(x_k)}{(x_k - q)(x_k - r)(x_k - s)},</math>

since

: <math>P - \frac{f(P)}{(P - q)(P - r)(P - s)} = P - 0 = P.</math>

Note that the denominator is still different from zero.

This fixed -point iteration is a [[contraction mapping]]

for ''x'' around ''P''.

The clue to the method now is to combine

the fixed -point iteration for ''P'' with similar iterations

for ''Q'', ''R'', ''S'' into a simultaneous iteration for all roots.

Initialize ''p'', ''q'', ''r'', ''s'':

: ''p''₀ := (0.4 + 0.9&nbsp;''i'')⁰ ;,

: ''q''₀ := (0.4 + 0.9&nbsp;''i'')¹ ;,

: ''r''₀ := (0.4 + 0.9&nbsp;''i'')² ;,

: ''s''₀ := (0.4 + 0.9&nbsp;''i'')³ ;.

There is nothing special about choosing 0.4&nbsp;+&nbsp;0.9&nbsp;''i'' except that it is neither a [[real number]] nor a [[root of unity]].

Make the substitutions for ''n'' = 1, 2, 3,&middot;&middot;&middot; ...:

|: <math> q_np_n = q_p_{n-1} - \frac{f(q_p_{n-1})}{ (q_p_{n-1} -p_n q_{n-1})(q_p_{n-1} - r_{n-1})(q_p_{n-1} - s_{n-1}) }; ,</math>

:{|

|: <math> r_nq_n = r_q_{n-1} - \frac{f(r_q_{n-1})}{ (r_q_{n-1} - p_n)(r_q_{n-1} -q_n r_{n-1})(r_q_{n-1} - s_{n-1}) }; ,</math>

|-

|: <math> p_nr_n = p_r_{n-1} - \frac{f(p_r_{n-1})}{ (p_r_{n-1} -q_{n-1} p_n)(p_r_{n-1} -r_{n-1} q_n)(p_r_{n-1} - s_{n-1}) }; ,</math>

|: <math> s_n = s_{n-1} - \frac{f(s_{n-1})}{ (s_{n-1} - p_n)(s_{n-1} - q_n)(s_{n-1} - r_n) }. </math>

|-

|<math> q_n = q_{n-1} - \frac{f(q_{n-1})}{ (q_{n-1}-p_n)(q_{n-1}-r_{n-1})(q_{n-1}-s_{n-1}) }; </math>

|-

|<math> r_n = r_{n-1} - \frac{f(r_{n-1})}{ (r_{n-1}-p_n)(r_{n-1}-q_n)(r_{n-1}-s_{n-1}) }; </math>

|-

|<math> s_n = s_{n-1} - \frac{f(s_{n-1})}{ (s_{n-1}-p_n)(s_{n-1}-q_n)(s_{n-1}-r_n) }. </math>

|}

Re-iterate until the numbers ''p'', ''q'', ''r'', ''s''

essentially stop changing relative to the desired precision.

They then have the values ''P'', ''Q'', ''R'', ''S'' in some order

and in the chosen precision. So the problem is solved.

Note that you must use [[complex number]] arithmetic must be used,

and that the roots are found simultaneously rather than one at a time.