Root-finding by iteration

Hassan2

Dear all,

I have a question about root-finding. In fact my problem is about solving system of nonlinear equations but I have simplified my question as follows:

Suppose I would like to find the root of the following function by iteration:

[itex]y=f(x,p(x))[/itex]

If I can calculate the total derivative with respect to x, I can use Newton-Raphson method effectively. However, for some reason, I can't calculate the total derivative. I can calculate the partial derivative though.

I am using the naive method of finding the root by "partial derivative". To this end, in each iteration I replace p(x) by its value evaluated from the previous value of x, treating it as a constant, and apply Newton-Raphson method. Convergence is achieved in most cases but I'm not sure if this is the right way.

My question is:

1. Is there a theory behind this method? Is it related to fixed-point iteration?

2. Does the convergence depend on p(x)?

Your help would be appreciated,

Hassan

chiro

Hey Hassan2.

Is this function just a 'complicated' (because of p(x)) one-dimensional function? This is what you seem to imply since y is only a function of x.

If this is the case, then in terms of the theory and application, the one-dimensional root finding methods like Newton-Rhapson and other similar ones should suffice provided that the function has the desired properties (like continuity, differentiability over a given interval). Hopefully this answers your first question.

For the second question, it depends on whether the function given p(x) has differentiability and continuity requirements fulfilled.

In terms of whether a root actually exists, then we can use the first derivative (might need the second for points of inflection) and the mean value theorem (or something similar) to show that a root exists given that the function is continuous (and differentiable).

If your function has the above properties, you will be able to use any root-finding algorithm for your function y (assuming only depends on x) and the algorithm should be able to tell you whether or not a real root even exists (although most algorithms generate complex roots as well).

Hassan2

Thanks a lot,



I think I should explains the original problem.

I have the following system of "nonlinear" equations in matrix form:

[itex]Ax=b[/itex]

A=A(x,p(x)) is a symmetric sparse matrix and the number of unknowns could be as many as one million. The matrix elements depend on p(x), with x being the vector of unknowns. Since p depends on all unknowns, the matrix of derivatives becomes non-sparse and , I guess, non-symmetric. That's why I can't use the derivatives. Beside that, the dependence of p(x) on x is complicated and is not in the form of a functional but it is evaluated by numerical methods.

The only method I know for solving system of nonlinear equations is the Newton-Raphson method. The method explained in my problem seems to be different and I have no material to support it. I am looking for a material which discusses the method.

Back to one dimensional problem,

can I solve the equation [itex]x^{3}-6=0[/itex]

by writing it as [itex]x^{2}x-6=0[/itex] and iterate as

[itex]x_{k}^{2}x_{k+1}-6=0[/itex]?

This example doesn't converge in my code.

Thanks again.

Hassan2

Sorry for the confusing setup of the problem.

After some research, I realized that the method is in fact the fixed point iteration method. In each iteration, the Newton-Raphson method first solve the following equation for [itex]x_{k+1}[/itex] .

[itex]f(x_{k+1},p(x_{k}))=0[/itex]

and yields the following fixed-point iteration:

[itex]x_{k+1}=g(x_{k})[/itex]

In the fixed-point method, the convergence depends both on g(x) and the starting point [itex]x_{0}[/itex] .