Numerical Analysis question

[[R_H]]

Got a quick (and potentially stupid) question about the n-th root algorithm.



When choosing the intial guess, it's x_k > A^(1/n) > A/((x_k)^(n-1)). I can't remember why A^(1/n) > A/((x_k)^(n-1)) nor can I find an explanation in my notes. I'd appreciate any help.

Thanks.

[Kuroneko]

Since A^{1/n} = A/[ (A^{1/n})^{n-1} ], x > A^{1/n} implies A^{1/n} > A/[ x^{n-1} ]. As for the first, x_k > A^{1/n} is a good idea because Newton's iteration error is quadratic with coefficient proportional to f"(x)/f'(x), which here means that slight overestimates have better convergence than slight underestimates.

[Edit: whoops, elementary error.]

[[R_H]]

Since A^{1/n} = A/[ (A^{1/n})^{n-1} ], x > A^{1/n} implies A^{1/n} > A/[ x^{n-1} ]. As for the first, x_k > A^{1/n} is a good idea because Newton's iteration error is quadratic with coefficient proportional to f"(x)/f'(x), which here means that slight overestimates have better convergence than slight underestimates.

[Edit: whoops, elementary error.]

Thank you.

A^{1/n} = A/[ (A^{1/n})^{n-1} ], that is if x_k were to be equal to A^(1/n)?

Another question, seeing how the n-th root algorithm is deriveable from Newton's Method, does it also have the same covergence rate (quadratic?)?

Thank you.

[Kuroneko]

A^{1/n} = A/[ (A^{1/n})^{n-1} ], that is if x_k were to be equal to A^(1/n)?

That equality is always true. The condition x_k > A^{1/n} means that replacing A^{1/n} with x in the denominator produces a lesser quantity, so that x_k > A^{1/n} = A/[ (A^{1/n})^{n-1} ] > A/[ (x_k)^{n-1} ].

Another question, seeing how the n-th root algorithm is deriveable from Newton's Method, does it also have the same covergence rate (quadratic?)?

Yes (yes).

[[R_H]]

Thank you for the explaination, everything is clear now.