Rootfinding for nonlinear equations

From Wikiversity
Jump to navigation Jump to search

 

Rootfinding for nonlinear equations


Numerical analysis > Rootfinding for nonlinear equations

Here we want to solve an equation of the kind .

Suppose that there exist such that . Then we want to construct a sequence , with , such that

The number is called root (of the function ).


Convergence[edit]

If the sequence defined by the numerical method converges, we can ask what the rate of convergence is. With this aim, we define the order of convergence of a sequence :

Definition (Order of convergence). A sequence converges to with order if

is the order of convergence of the numerical method that has generated the sequence . The constant is called rate of convergence. If and is between 0 and 1, the convergence is said to be linear convergence.Under the linear convergence condition,if , the sequence is said to converge superlinearly and if , then the sequence is said to converge sublinearly.

The quantity

represents the error at step . In general, with a numerical method, we do a finite number of iterations and for this reason we seek only an approximation of the true root . In particular, we can define a tolerance such that if ,we can stop the iteration and conclude that is the approximation of the true root.

Example[edit]

Suppose that the sequence converges to with order 2, where the constant , and suppose that the initial error . Consider a tolerance , then we can find the approximation of the true root by using the definition of convergence.Hence,

which is greater than the tolerance, so we should keep going until the error is less than the tolerance. We can get

which is also greater than the tolerance, thus we should do the iteration to calculate

which is still larger than the tolerance. Similarly,

which is less than the tolerance. Therefore, we can stop here and can conclude that is the approximation of the true root.


YangOu (talk) 02:44, 26 October 2012 (UTC)