
English: 
We have seen that Newton's method,
when it works, may work quite fast.
But that it also does not always work, it means that it does not always converge.
So in this video we will identify the conditions
that will guarantee the convergence of the method. And we'll also
try to characterize the speed of convergence.
Finally, we will show the equations that extend Newton's
method from one variable, to a system of n equations
with n variables. There are three conditions
that are sufficient to guarantee the convergence
of Newton's method. The first one is
that the function F must not be too non linear.
Actually, it makes sense when you think about it. Because Newton's method

French: 
Nous avons vu que la méthode de Newton,
quand elle fonctionne, peut fonctionner assez vite.
Mais qu'elle ne fonctionne pas toujours, c'est-à-dire qu'elle ne converge pas toujours.
Dans cette vidéo, nous allons identifier les conditions
qui garantiront la convergence de la méthode. Et nous allons aussi
essayer de caractériser la vitesse de convergence.
Enfin, nous allons montrer les équations qui généralisent la méthode de
Newton pour une variable à un système de n équations
à n variables. Il y a trois conditions
qui sont suffisantes pour garantir la convergence
de la méthode de Newton. La première est
que la fonction F ne doit pas être trop non linéaire.
En fait, c'est logique quand on y pense. Comme la méthode de Newton

French: 
s'appuie sur un modèle linéaire de la fonction,
si la fonction est vraiment très non linéaire, ce modèle
linéaire sera de mauvaise qualité et la méthode risque de ne pas bien fonctionner.
Si vous vous en souvenez, la manière de caractériser le niveau
de non-linéarité d’une fonction, repose sur le concept de
continuité au sens de Lipschitz. On dit que la
dérivée de F est continue au sens de Lipschitz
s'il existe une constante M qui soit
strictement positive, telle que la différence entre
les dérivées de F entre deux points, x et y,
est bornée par la distance entre x et y, multipliée
par cette constante M. Bien sûr, si M est très petite,
très proche de zéro, les deux valeurs ici seront aussi
très proches. Cela signifie que les dérivées de
la fonction sont proches, donc les pentes sont proches et la fonction

English: 
relies on a linear model of the function,
if the function is really badly non linear, this linear
model will be of poor quality, and the method may not work quite well.
If you remember, the way to characterize the level
of non linearity of a function, relies on the concept of
Lipschitz continuity. So we say that the
derivative of F is Lipschitz continuous
if there exists a constant M, which is
strictly positive, such that the difference between
the derivatives of F among two points, x and y,
is bounded by the distance between x and y, times
this constant M. Of course, if M is very small,
very close to zero, the two values here will be also
very close. It means that the derivative of
the function is close, so the slope is close, and the function

French: 
est proche d'être linéaire. Donc un petit M signifie une fonction qui est
presque linéaire. Un grand M signifie : la fonction est très
non linéaire. La deuxième condition est liée à la définition
de l'algorithme. Rappelez-vous, au cours de l'algorithme, nous devons
diviser par la dérivée de F. Et bien sûr, si elle est
nulle, ça ne marche pas. En réalité, si elle est proche de zéro,
cela ne fonctionnera pas très bien non plus. Donc la seconde
condition dit que la dérivée de la fonction
doit être bornée loin de zéro. Il existe un
rho constant, qui soit strictement positif, tel que 
la valeur absolue de la dérivée soit supérieure ou égale à rho pour tout x.
Donc, la dérivée est bornée loin de zéro, de sorte que nous pouvons diviser en toute sécurité
par la dérivée de F. Et la dernière
dit que la méthode fonctionnera si
nous commençons relativement près de la solution. Cela signifie qu’il existe un

English: 
is close to be linear. So small M means a function which is
almost linear. Big M means: the function is very
non linear. The second condition is related to the definition
of the algorithm. Remember, during the algorithm, we have to
divide by the derivative of F. And of course, if it is
zero, it does not work. But actually, if it is close to zero,
it will not work very well either. So the second
condition says that [for] the derivative of the function
must be bounded away from zero. So there exists a
constant rho, which is strictly positive, such that the
absolute value of the derivative is greater of equal to rho for any x.
So the derivative is bounded away from zero, so that we can safely divide
by the derivative of F. And the last
one says that the method will work if
we start it relatively close to the solution. So it means that there exists a

French: 
voisinage autour de la solution auquel le point de départ appartienne.
Et en fait, il s’agit d’une condition embêtante, car dans la pratique,
comment voulez-vous vous assurer de vérifier cela ? Comme on ne connait pas la solution.
N'est-ce pas ? C'est pour cela que nous utilisons un algorithme. Cela signifie qu’elle convergera vers une solution si elle
part d'un point qui est proche de la solution.
Et puis, il y a un théorème qui dit que
les itérés de la méthode de Newton qui sont rapportés ici
sont bien définis. Donc, il est valide de diviser par F'
de x_k car la dérivée est bornée loin de zéro.
La suite converge vers un point x étoile,
qui est en fait une racine de l'équation, et
elle converge q quadratiquement. Qu'est-ce que
cela veut dire, q-quadratique? Cela signifie que nous pouvons calculer
la distance entre l'itération suivante
et la solution, et cette distance est bornée

English: 
neighborhood around the solution in which the starting point belongs.
And actually, this is kind of an annoying condition, because in practice,
how do you want to make sure to verify that? Because you don't know the solution.
Right? This is why to use the algorithm. It means that it will converge to a solution if
it starts from a point which is close to the solution.
And then, there is a theorem that says that
the iterates of Newton's method that are reported here
are well defined. So it's valid to divide by F'
of x_k because the derivative is bounded away from zero.
The sequence converges to a point x star,
which is actually a root of the equation, and
it converges q-quadratically. So what
does it mean, q-quadratic? It means that we can calculate
the distance between the next iterate
and the solution, and this distance is bounded

English: 
by the distance of the previous iterate
x_k and the solution, squared.
Well, it's not that simple. There is also a constant that will
multiply this quantity, which involves the Lipschitz constant,
and the parameter rho that was defining the fact
that the derivative is bounded away from zero. So the
notion of q-quadratically comes from the fact that we have a two here.
So it means that, at each iteration, the precision of
the solution is doubled. Of course the quality
of this convergence, of the speed of convergence, will change with M.
So if M is small, the convergence
will be faster. Remember, if M is small,
the function is close to be linear. And in
the other direction, if M is bigger, then the convergence
will be slower. So when we have a very non linear function, Newton's

French: 
par la distance entre l'itération précédente
x_k et la solution, au carré.
En fait, ce n'est pas si simple. Il y a aussi une constante qui va
multiplier cette quantité, qui implique la constante de Lipschitz,
et le paramètre rho qui définissait le fait
que la dérivée soit bornée loin de zéro. La
notion de q-quadratique vient du fait que nous avons un "deux" ici.
Cela signifie donc que, à chaque itération, la précision de
la solution est doublée. Bien sûr, la qualité
de cette convergence, de la vitesse de convergence, va changer avec M.
Donc, si M est petit, la convergence
sera plus rapide. Rappelez-vous, si M est petit,
la fonction est proche d'être linéaire. Et
dans l'autre sens, si M est plus grand, alors la convergence
sera plus lente. Donc, quand nous avons une fonction très non linéaire, la méthode de

French: 
Newton sera plus lente. L'influence du paramètre rho
va dans l'autre sens, car il apparaît au dénominateur.
Ainsi quand rho est grand,
nous aurons une convergence rapide. Qu'est-ce que cela signifie ? Quand
rho est grand, cela signifie que la dérivée de F est très loin de zéro.
Et dans l'autre sens, quand rho est petit,
cela ralentit la vitesse
de convergence de la méthode. Quand rho est petit, cela signifie
que la dérivée de F est proche de zéro.
La preuve du théorème sort du cadre
de ce cours. Si vous êtes intéressé, vous pouvez regarder le théorème 7.7 dans le livre.
Nous avons vu ces concepts dans le contexte d’une
équation à une variable, parce que c'était plus simple. Mais ils
s'étendent directement au cas d'un système de n équations à n
variables. Ecrivons les équations pour obtenir la

English: 
method will be slower. So the influence of parameter rho
goes into the other direction, because it appears at the denominator.
So when rho is big,
we will have a fast convergence. So what does it mean? When
rho is big, it means that the derivative of F is very far away from zero.
And in the other direction, when rho is small,
it slows down the speed
of the convergence of the method. When rho is small, it means
that the derivative of F is close to zero.
So the proof of the theorem is out of the scope
of this course. If you are interested, you can look at Theorem 7.7 in the book.
We have seen these concepts in the context of one
equation of one variable, because it was simpler. But they
extend directly to the case of a system of n equations with n
variables. So let's write down the equations to get the

English: 
version of Newton's method for n equations and n variables.
Here, the statement of the problem involves a function which takes n
variables and returns n values. So these are the n equations. 
And we would like to find x such that F(x) is
equal to zero. So this is the statement of the problem. Let's remember
the definition of the gradient matrix.
So the gradient matrix is a matrix in which each
column is the gradient of the corresponding equation.
So this the gradient of equation 1, equation 2, up to equation n.
This is another way to write this
gradient matrix. But sometimes, and it's actually the case
in the context of Newton's method, it's convenient to use the transpose
of this matrix, which is then called the Jacobian. So the Jacobian 
matrix is a matrix where each row corresponds
to the derivatives of the... of a different equation.

French: 
version de la méthode de Newton pour n équations et n variables.
Ici, l'énoncé du problème implique une fonction qui prend n
variables et retourne n valeurs. Donc, ce sont les n équations.
Et nous aimerions trouver x tel que F(x) est
égal à zéro. C'est donc l'énoncé du problème. Souvenons-nous de
la définition de la matrice gradient.
La matrice gradient est une matrice dans laquelle chaque
colonne est le gradient de l'équation correspondante.
Donc, ceci est le gradient de l'équation 1, l'équation 2, jusqu'à l'équation n.
Ceci est une autre façon d'écrire cette
matrice gradient. Mais parfois, et c'est en fait le cas
dans le contexte de la méthode de Newton, il est pratique d'utiliser la transposée
de cette matrice, qui s'appelle alors le Jacobien. Donc la matrice
jacobienne est une matrice où chaque ligne correspond
aux dérivées d'une équation différente.

French: 
La méthode de Newton repose sur un modèle linéaire. Quel est
le modèle linéaire dans le contexte d'une fonction de
R^n dans R^n ? Eh bien, c'est fondamentalement la même chose. Nous utilisons le théorème de Taylor.
Nous avons la valeur de la fonction en
x chapeau, plus la matrice gradient
transposée, fois x
moins x chapeau. Ou,
nous pouvons l'écrire en utilisant le Jacobien,
parce que le Jacobien est la transposée de la matrice
gradient. Nous avons le Jacobien fois x
moins x chapeau. Et maintenant les itérations
de la méthode de Newton sont les suivantes. Nous avons
l'itéré actuel x_k, qui est un vecteur de
R^n. Et puis nous
le complétons en utilisant la direction d_k, qui est aussi

English: 
So Newton's method relies on a linear model. What is
a linear model in the context of a function from
R^n to R^n. Well, it's basically the same. We use Taylor's theorem.
So we have the value of the function at
x hat, plus the gradient matrix
transposed, times x
minus x hat. Or,
we can write it using the Jacobian,
because the Jacobian is the transpose of the gradient
matrix. We have the Jacobian times x 
minus x hat. And now the iterations
of Newton's method are as follows. So we have
the current iterate x_k, which is a vector of
R^n. And then we
complete it using a direction d_k, which is also

English: 
a vector of R^n, that solves
the system of linear equations defined
by the Jacobian. So this is the Jacobian, times d_k
is equal to minus F of
x_k. So, if the Jacobian is invertible,
which we'll assume it is, we will have
the Jacobian
inverse times the value of the function.
OK. So we have a very similar
format as in the one dimensional case. So it's
minus the value of the function divided by the derivative. And this is now
written using matrices and vectors.
So in this video, we have identified the conditions for which
the method will converge. We have seen three of them. The function
cannot be too non linear. The derivative of the function

French: 
un vecteur de R^n, qui résout
le système d'équations linéaires défini
par le Jacobien. C'est le Jacobien, fois d_k
est égal à moins F de
x_k. Donc, si le Jacobien est inversible,
ce que nous supposerons, nous aurons
le Jacobien
inverse fois la valeur de la fonction.
OK. Nous avons donc un format très
similaire au cas à une dimension. C'est
moins la valeur de la fonction divisée par la dérivée. Mais c'est maintenant
écrit en utilisant des matrices et des vecteurs.
Dans cette vidéo, nous avons identifié les conditions pour lesquelles
la méthode va converger. Nous en avons vu trois. La fonction
ne peut pas être trop non linéaire. La dérivée de la fonction

English: 
should be bounded away from zero. And the starting point of the iterates
should not be too far away from the solution.
We have also characterized the speed of convergence,
that we called quadratic, or q-quadratically
convergent, was the exact terms. So basically, roughly speaking, it means
that the precision will double at each iteration.
And finally, we have provided the equations that
generalize the method of Newton from
one equation with one variable, to a system of n
equations and n variables.

French: 
devrait être bornée loin de zéro. Et le point de départ des itérés
ne devrait pas être trop loin de la solution.
Nous avons également caractérisé la vitesse de convergence,
que nous avons appelée quadratique, ou q-quadratiquement
convergent, étaient les termes exacts. Donc, en gros, cela signifie
que la précision double à chaque itération.
Et enfin, nous avons fourni les équations qui
généralisent la méthode de Newton de
une équation à une variable, à un système de n
équations et n variables.
