## Root-finding by iteration

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:

$y=f(x,p(x))$

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
 PhysOrg.com science news on PhysOrg.com >> Ants and carnivorous plants conspire for mutualistic feeding>> Forecast for Titan: Wild weather could be ahead>> Researchers stitch defects into the world's thinnest semiconductor

 Quote by 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: $y=f(x,p(x))$ 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
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).
 Thanks a lot, I think I should explains the original problem. I have the following system of "nonlinear" equations in matrix form: $Ax=b$ 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 $x^{3}-6=0$ by writing it as $x^{2}x-6=0$ and iterate as $x_{k}^{2}x_{k+1}-6=0$? This example doesn't converge in my code. Thanks again.

## Root-finding by iteration

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 $x_{k+1}$ .

$f(x_{k+1},p(x_{k}))=0$

and yields the following fixed-point iteration:

$x_{k+1}=g(x_{k})$

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

 Tags newton-raphson
 Thread Tools

 Similar Threads for: Root-finding by iteration Thread Forum Replies Programming & Comp Sci 5 Calculus & Beyond Homework 3 Precalculus Mathematics Homework 10 Calculus 5 Precalculus Mathematics Homework 10