Lecture 5 : Solving nonlinear systems

May, 2022 - François HU

Master of Science - EPITA

This lecture is available here: https://curiousml.github.io/

image-2.png

Table of contents

  1. Objective

  2. Bisection method

  3. Fixed-point iteration method

  4. Newton's method

  5. Exercices

  1. Solving $A\times X = B$

1. Objective

1.1. Nonlinear systems

In linear systems: $$ \begin{bmatrix} a_{0,0} & a_{0,1} & \cdots & a_{0,n-1} \\ a_{1,0} & a_{1,1} & \cdots & a_{1,n-1} \\ & \vdots & \\ a_{n-1,0} & a_{n-1,1} & \cdots & a_{n-1,n-1} \end{bmatrix} \times \begin{bmatrix} x_0\\ x_1\\ \vdots\\ x_{n-1} \end{bmatrix} = \begin{bmatrix} b_0\\ b_1\\ \vdots\\ b_{n-1} \end{bmatrix}\iff Ax - b = 0 $$

In nonlinear systems: $$ f(x) = 0 $$

We wish to find a solution to the non linear equation $f(x) = 0$ with $x = \begin{bmatrix} x_0\\ x_1\\ \vdots\\ x_{n-1} \end{bmatrix}$ the unkwown variable in the form of a "floating point" number. An equation of this type may have none, one or more solutions. We will assume that it has at least one which we will try to determine.

1.2. Condition number

We quantity the condition number that measures how sensitive the output of a function is on its input:

$$ \text{change in output} = \text{condition number}\times \text{change in input} $$

1.3. Order of convergence

a solution $x^*$ is called simple if $f(x^*) = 0$ and $f'(x^*) \neq 0$

$$ \lim\limits_{k\to\infty} \dfrac{ x_{k+1} - x^* }{ \lvert\lvert x_{k} - x^* \lvert\lvert^q } = r $$

2. Bisection method

image-2.png

Pseudo-code

bisection(f, a, b, eps)
    Input : function f, extremities a and b, precision eps
    Output : m such that |b-a| < eps

    while b - a >= eps do:
        m = (a+b)/2
        if f(a) x f(m) > 0 do:
            a = m
        else:
            b = m

Remarks:

3. Fixed-point iteration method

image.png

image-2.png

Remarks:

Let us denote $g$ a function verifying: $g(x^*) = x^*$.

4. Newton's method