May, 2022 - François HU
Master of Science - EPITA
This lecture is available here: https://curiousml.github.io/
bisection
algorithmfixed_point
algorithmnewton
algorithmIn 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.
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} $$a solution $x^*$ is called simple if $f(x^*) = 0$ and $f'(x^*) \neq 0$
for each iteration we are $q$ times more precise.
if $q=1$ the convergence is called a linear convergence,
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:
Remarks:
Let us denote $g$ a function verifying: $g(x^*) = x^*$.