Os Métodos Numéricos

[pic 1]

Iterative Numerical Methods

[pic 2]

Subject: Numerical Methods

Teacher: Mr. George Mahalu

Erasmus Student:  Fernando Jorge Andrade

 Wilton Rodrigues 

Summary

Introduction        3

Iterative numerical methods for nonlinear system        4

∙        Newton method        5

∙        Secant Method        7

Iterative numerical methods for linear system        9

∙        The Jacobi Method        9

∙        Gauss-Seidel Method        12

Introduction

This paper elaborated by Fernando Jorge Andrade, of the course of Computer science of management and Wilton Rodrigues, of the course of electrotechnical engineering, in the scope of the discipline numerical methods, aims to define, to explain some of the iterative numerical methods for resolution of linear and nonlinear systems, as well as exemplified in the Scilab software.

        

Iterative numerical methods for nonlinear system

In most cases, iterative methods are needed to of equations when the equations are non-linear.

The iterative methods discussed here are of the  = Ф(). These provide a vector sequence ∞k=0, where  is the index of the step (or iteration) and the approximation of the solution in k-th iteration. From an initial estimate , this sequence may diverge or converge to a root  of the system F(x) = 0.[pic 3][pic 4][pic 5][pic 6][pic 7][pic 8][pic 9]

Solving a system of nonlinear equations is a problem that is avoided whenever possible, usually by approaching the nonlinear system by a system of linear equations. When this is not possible, the simplest approach is

to adapt the methods that determine the approximate solutions of a single nonlinear equation in a variable, replacing the problem of a variable with a vector problem that incorporates all the variables

• Newton method

The Newton Method (or Newton-Raphson) is probably the most widely used algorithm for obtaining the solution of systems of non-linear equations. The method is basically given by equation.

                                                [pic 10]

Generally, one expects to obtain a quadratic convergence, provided that an initial value close to the solution is known and that   exists.[pic 11]

A weak point in Newton's method arises from the need to calculate the Jacobian matrix J(x) and solve a linear system at each iteration for the calculation of its inverse (x).[pic 12]

In its implementation, the explicit computation of (x) and product  can be avoided by solving the system =  to determine the vector . Then, the new approximation () is obtained by adding  to . This operation aims to reduce the computational effort required in each iteration of Newton's method. Whenever feasible, this technique will be used in the other methods.[pic 13][pic 14][pic 15][pic 16][pic 17][pic 18][pic 19][pic 20]

Newton's method has the following geometric interpretation.

Consider the line tangent to f at point   given by [pic 21]

.[pic 22]

Define  as the root of L, which can be seen as a linear approximation of f in the neighborhood of .[pic 23][pic 24]

Formally,  if, and only if,  .[pic 25][pic 26]

Algorithm

INTPUT: Function f and its derivative f’; initial approximation .[pic 27]

DATA: Maximum number of interactions ; tolerances  e .[pic 28][pic 29][pic 30]

Initialize: K = 0,  =  e Dr = [pic 31][pic 32][pic 33]

WHILE  K ,  make[pic 34][pic 35]

        Update: k = k +1

        Define: X = .[pic 36]

        Calculate: .[pic 37]

        Update: [pic 38]

        Evaluate:  = [pic 39][pic 40]

OUTPUT: Approximation to root x.

Example

Use Newton's method to find an estimate for the positive root of the function

[pic 41]

with initial approximation  and tolerances  e [pic 42][pic 43][pic 44]

First, note that

              and     [pic 45][pic 46]

Beginning with the initial approximation , we construct the table in which [pic 47][pic 48]

K	[pic 49]	[pic 50]	[pic 51]	Dr
0	1.00000	-0.28172	0.71828	0.39221
1	1.39221	0.23932	2.02374	0.11825
2	1.273957	0.027057	-	-

We finish the iterations because the condition | | <  was satisfied[pic 52][pic 53]

Scilab example:

[pic 54]

deff('y = f(x)','y = x.^2 -x -2')                            //Function

deff('y = f1(x)','y = 2*x -1')                               //derived from the function

x0=3                                                                  //initial approach

x1= x0 - (f(x0)/f1(x0))                                      //formula first interaction