# Fixed point,, Jacobi- & Newton Method, Linear Systems

• MHB
• mathmari
In summary, the Jacobi method will not converge for the second linear system as it is not strictly diagonally dominant.
mathmari
Gold Member
MHB
Hey! :giggle:

Question 1 :
Let $g(x)-=x-x^3$. The point $x=0$ is a fixed point for $g$. Show that if $x^{\star}$ is a fixed point of $g$, $g(x^{\star})=x^{\star}$, then $x^{\star}=0$. If $(x_k)$ the sequence $x_{k+1}=g(x_k)$, $k=0,1,2,\ldots$ show that if $0>x_0>-1$ then $(x_k)$ is increasing and converges to $0$.

My solution :
$g(x)=x-x^3$
$g(0)=0$
$g(x^{\star})=x^{\star} \Rightarrow x^{\star} -{x^{\star}}^3=x^{\star} \Rightarrow {x^{\star}}^3=0 \Rightarrow x^{\star} =0$
$x_{k+1}=g(x_k)$
$0>x_0>-1$
We have that $g'(x)=1-3x^2$ and $g'(x)=0 \Rightarrow 3x^2=1 \Rightarrow x^2=\frac{1}{3} \Rightarrow x=\pm\frac{1}{\sqrt{3}}$.
Then $g'(x)>0$ for $-\frac{1}{\sqrt{3}}<x<\frac{1}{\sqrt{3}}$ and $g'(x)\leq 0$ for $x\leq -\frac{1}{\sqrt{3}}$and $x\geq \frac{1}{\sqrt{3}}$.
So $g$ is increasing at $\left (-\frac{1}{\sqrt{3}}, \frac{1}{\sqrt{3}}\right )$ so the sequence $(x_k)$ is increasing in that interval.
Then $x_0<0 \Rightarrow x_{k+1}g(x_k)<g(x^{\star})=x^{\star}$. Increasing and upper bounded sequence, so it converges to $x^{\star}=0$.
Question 2 :
We consider the linear system \begin{align*}&3x+y=1 \\ &x+2y=3\end{align*} If we know that if we apply Jacobi Method tosolve the above linear system, it would converge, then check if Jacobi mathod converges if we apply it for the linear system \begin{align*}&x+2y=3 \\ &3x+y=1\end{align*}

My solution :
At the initial system we have the symmetric matrix $A=\begin{pmatrix}3 & 1 \\ 1 & 2\end{pmatrix}$. At the second system we have the matrix $\tilde{A}=\begin{pmatrix}1 & 2 \\ 3 & 1\end{pmatrix}$. This matrix is not symmetric neither it is diagonally dominant. So we don't have convergence.
Question 3 :
Let $x,y,\epsilon_1, \epsilon_2\in \mathbb{R}$ such that \begin{align*}&3x+y=7+\epsilon_1 \\ &4x+2y=10+\epsilon_2\end{align*} Show that $|x-2|+|y-1|\leq 3(|\epsilon_1|+|\epsilon_2|)$.

My solution :
From the first equation we get $y=7+\epsilon_1-3x\ \ \ \ \ (\star)$.
Substituting this in the second equation we get \begin{align*}4x+2(7+\epsilon_1-3x)=10+\epsilon_2 &\Rightarrow 4x+14+2\epsilon_1-6x=10+\epsilon_2 \\ & \Rightarrow -2x=-4+\epsilon_2-2\epsilon_1 \\ & \Rightarrow x=2-\frac{\epsilon_2}{2}+\epsilon_1\end{align*}
Substituting this $(\star)$ we get \begin{equation*}y=7+\epsilon_1-6+\frac{3}{2}\epsilon_2-3\epsilon_1=1-2\epsilon_1+\frac{3}{2}\epsilon_2\end{equation*}
Then \begin{align*}|x-2|+|y-1|&=\left |2-\frac{\epsilon_2}{2}+\epsilon_1-1\right |+\left |1-2\epsilon_1+\frac{3}{2}\epsilon_2-1\right |\\ & = \left |\epsilon_1-\frac{\epsilon_2}{2}\right |+\left |-2\epsilon_1+\frac{3}{2}\epsilon_2\right |\\ & \leq |\epsilon_1|+\frac{|\epsilon_1|}{2}+2|\epsilon_1|+\frac{3}{2}|\epsilon_2| \\ & = 3|\epsilon_1|+2|\epsilon_2| \\ & \leq 3|\epsilon_1|+3|\epsilon_2| = 3\left (|\epsilon_1|+|\epsilon_2| \right )\end{align*}
Question 4 :
Let $f(x)=x-x^3$. Let $(x_k)$ be the sequence that we get if we consider Newton's method to approximate a root. If $x_0=-\frac{1}{\sqrt{5}}$, then does the sequence converge? Is yes, find the limit.

My solution :
We have that $f'(x)=1-3x^2$.
Then \begin{equation*}x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)} \Rightarrow x_{n+1}=x_n-\frac{x_n-x_n^3}{1-3x_n^2}=-\frac{2x_n^3}{1-3x_n^2}\end{equation*}
Let $g(x)=-\frac{2x_n^3}{1-3x_n^2}$.
$x_1=g(x_0)=g\left (-\frac{1}{\sqrt{5}}\right )$.
\begin{equation*}\left |g'(x)\right |=\left |-\frac{6x^2}{(1-3x^2)^2}\right |=\frac{6x^2}{(1-3x^2)^2}\end{equation*}
We have that \begin{equation*}|g'(x)|<1 \Rightarrow 6x^2<1-6x^2+9x^4 \Rightarrow 9x^4-12x^2+1<0\end{equation*}
Are my solutions correct ? :unsure:

mathmari said:
Then $g'(x)>0$ for $-\frac{1}{\sqrt{3}}<x<\frac{1}{\sqrt{3}}$ and $g'(x)\leq 0$ for $x\leq -\frac{1}{\sqrt{3}}$and $x\geq \frac{1}{\sqrt{3}}$.
So $g$ is increasing at $\left (-\frac{1}{\sqrt{3}}, \frac{1}{\sqrt{3}}\right )$ so the sequence $(x_k)$ is increasing in that interval.
Then $x_0<0 \Rightarrow x_{k+1}g(x_k)<g(x^{\star})=x^{\star}$. Increasing and upper bounded sequence, so it converges to $x^{\star}=0$.

Let's see...
Consider $f: x\mapsto x-1$, which has $f'(x)=1>0$ so it's increasing.
But a sequence $(x_k)$ with $x_{k+1}=f(x_k)$ won't be increasing, will it?

Klaas van Aarsen said:
Let's see...
Consider $f: x\mapsto x-1$, which has $f'(x)=1>0$ so it's increasing.
But a sequence $(x_k)$ with $x_{k+1}=f(x_k)$ won't be increasing, will it?

Ahh yes, the sequence is decreasing... So what could we do instead? :unsure:

mathmari said:
Ahh yes, the sequence is decreasing... So what could we do instead?
Hint: we need that $|x_{k+1}|=|g(x_k)|<|x_k|$.

mathmari said:
Question 2 :
We consider the linear system \begin{align*}&3x+y=1 \\ &x+2y=3\end{align*} If we know that if we apply Jacobi Method to solve the above linear system, it would converge, then check if Jacobi mathod converges if we apply it for the linear system \begin{align*}&x+2y=3 \\ &3x+y=1\end{align*}

My solution :
At the initial system we have the symmetric matrix $A=\begin{pmatrix}3 & 1 \\ 1 & 2\end{pmatrix}$. At the second system we have the matrix $\tilde{A}=\begin{pmatrix}1 & 2 \\ 3 & 1\end{pmatrix}$. This matrix is not symmetric neither it is diagonally dominant. So we don't have convergence.

The Jacobi method is intended for strictly diagonally dominant systems. It doesn't say what it will do for systems that are not.
I think we need to try to apply it to see if it will converge or not.

Klaas van Aarsen said:
Hint: we need that $|x_{k+1}|=|g(x_k)|<|x_k|$.

We have that $|x_{k+1}|=|g(x_k)|=|x_k-x_k^3|=|x_k|\cdot |1-x_k^2|$. So we have to show that $|1-x_k^2|<1$, right? :unsure:
Klaas van Aarsen said:
The Jacobi method is intended for strictly diagonally dominant systems. It doesn't say what it will do for systems that are not.
I think we need to try to apply it to see if it will converge or not.

So there is no relation between the two systems, I mean as for the convergence of the method, is there?

From the second system we get : $$\begin{pmatrix}1 & 2 \\ 3 & 1\end{pmatrix}=\begin{pmatrix}0 & 0 \\ 3 & 0\end{pmatrix}+\begin{pmatrix}1 & 0 \\ 0 & 1\end{pmatrix}+\begin{pmatrix}0 & 2 \\ 0 & 0\end{pmatrix} =L+D+U$$
The method converges if the spectral radius of $D^{-1}(D-A)$ isless than $1$, right?
We have that $$D^{-1}(D-A)=\begin{pmatrix}1 & 0 \\ 0 & 1\end{pmatrix}\begin{pmatrix}0 & -2 \\ -3 & 0\end{pmatrix}=\begin{pmatrix}0 & -2 \\ -3 & 0\end{pmatrix}$$ The eigenvalues are $\pm \sqrt{6}$, so the spectral radius is greater than $1$, and so we don't have convergence.

Is that correct? :unsure:

mathmari said:
We have that $|x_{k+1}|=|g(x_k)|=|x_k-x_k^3|=|x_k|\cdot |1-x_k^2|$. So we have to show that $|1-x_k^2|<1$, right?

That could work.

Alternatively we have $|x_{k+1}|=|g(x_k)|<|x_k| \implies \left|\frac{g(x_k) - 0}{x_k-0}\right| < 1$.
That is, if $g$ is Lipschitz continuous on the interval with a constant less than $1$, then the iterative method converges.
mathmari said:
So there is no relation between the two systems, I mean as for the convergence of the method, is there?

From the second system we get : $$\begin{pmatrix}1 & 2 \\ 3 & 1\end{pmatrix}=\begin{pmatrix}0 & 0 \\ 3 & 0\end{pmatrix}+\begin{pmatrix}1 & 0 \\ 0 & 1\end{pmatrix}+\begin{pmatrix}0 & 2 \\ 0 & 0\end{pmatrix} =L+D+U$$
The method converges if the spectral radius of $D^{-1}(D-A)$ is less than $1$, right?
We have that $$D^{-1}(D-A)=\begin{pmatrix}1 & 0 \\ 0 & 1\end{pmatrix}\begin{pmatrix}0 & -2 \\ -3 & 0\end{pmatrix}=\begin{pmatrix}0 & -2 \\ -3 & 0\end{pmatrix}$$ The eigenvalues are $\pm \sqrt{6}$, so the spectral radius is greater than $1$, and so we don't have convergence.

Is that correct?
The method indeed converges if the spectral radius is less than $1$.

The converse is not necessarily true though. (Worried)

mathmari said:
Question 3 :
...

Then \begin{align*}|x-2|+|y-1|&=\left |2-\frac{\epsilon_2}{2}+\epsilon_1-{\color{red}\mathbf{1}}\right |+\left |1-2\epsilon_1+\frac{3}{2}\epsilon_2-1\right |\\ & = \left |\epsilon_1-\frac{\epsilon_2}{2}\right |+\left |-2\epsilon_1+\frac{3}{2}\epsilon_2\right |\\ & \leq |\epsilon_1|+\frac{|\epsilon_1|}{2}+2|\epsilon_1|+\frac{3}{2}|\epsilon_2| \\ & = 3|\epsilon_1|+2|\epsilon_2| \\ & \leq 3|\epsilon_1|+3|\epsilon_2| = 3\left (|\epsilon_1|+|\epsilon_2| \right )\end{align*}

All good. (Nod)
You do have a ${\color{red}\mathbf{1}}$ that I've marked in red that should be a $2$ though.

mathmari said:
Question 4 :
Let $f(x)=x-x^3$. Let $(x_k)$ be the sequence that we get if we consider Newton's method to approximate a root. If $x_0=-\frac{1}{\sqrt{5}}$, then does the sequence converge? Is yes, find the limit.

My solution :
We have that $f'(x)=1-3x^2$.
Then \begin{equation*}x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)} \Rightarrow x_{n+1}=x_n-\frac{x_n-x_n^3}{1-3x_n^2}=-\frac{2x_n^3}{1-3x_n^2}\end{equation*}
Let $g(x)=-\frac{2x_n^3}{1-3x_n^2}$.
$x_1=g(x_0)=g\left (-\frac{1}{\sqrt{5}}\right )$.
\begin{equation*}\left |g'(x)\right |=\left |-\frac{6x^2}{(1-3x^2)^2}\right |=\frac{6x^2}{(1-3x^2)^2}\end{equation*}
We have that \begin{equation*}|g'(x)|<1 \Rightarrow 6x^2<1-6x^2+9x^4 \Rightarrow 9x^4-12x^2+1<0\end{equation*}
This seems incomplete.
How do you know it converges?
What did you find for the limit?

## 1. What is a fixed point method?

A fixed point method is a numerical method used to find the root of a function. It involves repeatedly applying a function to an initial guess until the result converges to a fixed point, which is the root of the original function.

## 2. How does the Jacobi method work?

The Jacobi method is an iterative algorithm used to solve linear systems of equations. It involves splitting the system into two parts and using the values from the previous iteration to update the current values until the solution converges.

## 3. What is the Newton method used for?

The Newton method, also known as the Newton-Raphson method, is a numerical method used to find the roots of a function. It involves using the derivative of the function to iteratively improve the initial guess until the root is found.

## 4. How do you solve linear systems using the Jacobi method?

To solve a linear system using the Jacobi method, the system must first be written in matrix form. Then, an initial guess for the solution is chosen and the system is split into two parts. The values from the previous iteration are used to update the current values until the solution converges.

## 5. What are the advantages of using the Newton method?

The Newton method has several advantages, including its fast convergence rate and ability to find multiple roots. It is also relatively simple to implement and can be applied to a wide range of functions. However, it may not always converge and can be sensitive to the initial guess.

Replies
17
Views
3K
Replies
1
Views
913
Replies
4
Views
860
Replies
8
Views
1K
Replies
9
Views
4K
Replies
4
Views
1K
Replies
21
Views
3K
Replies
2
Views
822
Replies
4
Views
978
Replies
6
Views
1K