Summary

Functional (Fixed-Point) Iteration

만약 g가 어떤 p$\in$[a,b]에 대해 [a,b]와 g(p)=p에 정의된다면, 함수 g는 [a,b]에서 고정점 p를 갖는다.

Intermediate Value Therem

만약 f$\in$[a,b]와 K가 f(a)와 f(b) 사이의 임의의 수라면, f(c)=K인 수 c$\in$(a,b)가 존재한다.

Uniqueness Result

모든 $x \in[a, b]$에 대해 $g \in C[a, b]$와 $g(x) \in[a, b]$로 하자. 또한 $g^{\prime}(x)$가 $(a, b)$에 존재한다면

그렇다면 함수 $g$는 $[a, b]$에서 고유한 고정점 $p$를 갖는다.

Convergence Result

Let $g \in C[a, b]$ with $g(x) \in[a, b]$ for all $x \in[a, b]$. Let $g^{\prime}(x)$ exist on $(a, b)$ with

If $p_0$ is any point in $[a, b]$ then the sequence defined by

will converge to the unique fixed point $p$ in $[a, b]$.

Corrollary to the Convergence Result

If $g$ satisfies the hypothesis of the Theorem, then

Introduction & Theoretical Framework

Functional (Fixed-Point) Iteration

Prime Objective

• In what follows, it is important not to lose sight of our prime objective:
• Given a function $f(x)$ where $a \leq x \leq b$, find values $p$ such that $f(p)=0$
• Given such a function, $f(x)$, we now construct an auxiliary function $g(x)$ such that
  $p=g(p)$
  whenever $f(p)=0$ (this construction is not unique).
• The problem of finding $p$ such that $p=g(p)$ is known as the fixed point problem.

a≤x≤b인 함수 f(x)가 주어졌을 때, f(p)=0인 값 p를 구한다.
이러한 함수 f(x)가 주어지면, 우리는 이제 p=g(p)와 같은 보조 함수 g(x)를 구성한다.
f(p)=0일 때마다(이 구조는 unique하지 않음).
p=g(p)가 되는 p를 찾는 문제를 고정점 문제라고 한다

Functional (Fixed-Point) Iteration

A Fixed Point

If $g$ is defined on $[a, b]$ and $g(p)=p$ for some $p \in[a, b]$, then the function $g$ is said to have the fixed point $p$ in $[a, b]$.

만약 g가 어떤 pθ[a,b]에 대해 [a,b]와 g(p)=p에 정의된다면, 함수 g는 [a,b]에서 고정점 p를 갖는다고 한다.

Note

• The fixed-point problem turns out to be quite simple both theoretically and geometrically.
• The function $g(x)$ will have a fixed point in the interval $[a, b]$ whenever the graph of $g(x)$ intersects the line $y=x$.

고정점 문제는 이론적으로나 기하학적으로나 꽤 간단한 것으로 밝혀졌다.
함수 g(x)는 g(x)의 그래프가 y=x선과 교차할 때마다 구간 [a,b]에서 고정점을 갖는다.

The Equation $f(x)=x-\cos (x)=0$

If we write this equation in the form:

then $g(x)=\cos (x)$

Single Nonlinear Equation f(x)=x-cos(x)=0

Functional (Fixed-Point) Iteration

Existence of a Fixed Point

If $g \in C[a, b]$ and $g(x) \in[a, b]$ for all $x \in[a, b]$ then the function $g$ has a fixed point in $[a, b]$.

Proof

• If $g(a)=a$ or $g(b)=b$, the existence of a fixed point is obvious.
• Suppose not; then it must be true that $g(a)>a$ and $g(b)<b$.
• Define $h(x)=g(x)-x ; h$ is continuous on $[a, b]$ and, moreover,
  $h(a)=g(a)-a>0, \quad h(b)=g(b)-b<0 .$
• The Intermediate Value Theorem \&ivi implies that there exists $p \in(a, b)$ for which $h(p)=0$.
• Thus $g(p)-p=0$ and $p$ is a fixed point of $g$.

Intermediate Value Theorem

If $f \in C[a, b]$ and $K$ is any number between $f(a)$ and $f(b)$, then there exists a number $c \in(a, b)$ for which $f(c)=K$.

만약 f$\in$[a,b]와 K가 f(a)와 f(b) 사이의 임의의 수라면, f(c)=K인 수 c$\in$(a,b)가 존재한다.

$g(x)$ has a Fixed Point in $[a,b]$.

Illustration

• Consider the function $g(x)=3^{-x}$ on $0 \leq x \leq 1 . g(x)$ is continuous and since
  $g^{\prime}(x)=-3^{-x} \log 3<0 \quad \text { on }[0,1]$
  $g(x)$ is decreasing on $[0,1]$.
• Hence
  $g(1)=\frac{1}{3} \leq g(x) \leq 1=g(0)$
  i.e. $g(x) \in[0,1]$ for all $x \in[0,1]$ and therefore, by the preceding result, $g(x)$ must have a fixed point in $[0,1]$.

Functional (Fixed-Point) Iteration

An Important Observation

• It is fairly obvious that, on any given interval $I=[a, b], g(x)$ may have many fixed points (or none at all).
• In order to ensure that $g(x)$ has a unique fixed point in I, we must make an additional assumption that $g(x)$ does not vary too rapidly.
• Thus we have to establish a uniqueness result.

주어진 간격 $I=[a,b]에서 g(x)$는 많은 고정점을 가질 수 있다는 것은 꽤 명백하다.
$g(x)$가 I에서 고유한 고정점을 가지도록 하려면 $g(x)$가 너무 빠르게 변하지 않는다는 추가 가정을 해야 한다.
따라서 우리는 특이성 결과를 확립해야 한다.

Uniqueness Result

Let $g \in C[a, b]$ and $g(x) \in[a, b]$ for all $x \in[a, b]$. Further if $g^{\prime}(x)$ exists on $(a, b)$ and

모든 $x \in[a, b]$에 대해 $g \in C[a, b]$와 $g(x) \in[a, b]$로 하자. 또한 $g^{\prime}(x)$가 $(a, b)$에 존재한다면

then the function $g$ has a unique fixed point $p$ in $[a, b]$

그렇다면 함수 $g$는 $[a, b]$에서 고유한 고정점 $p$를 갖는다.

Unique Fixed Point: $\left|g^{\prime}(x)\right| \leq 1$ for all $x \in[a, b]$

Functional (Fixed-Point) Iteration

Proof of Uniqueness Result

• Assuming the hypothesis of the theorem, suppose that $p$ and $q$ are both fixed points in $[a, b]$ with $p \neq q$.
• By the Mean Value Theorem a millustration, a number $\xi$ exists between $p$ and $q$ and hence in $[a, b]$ with
  $\begin{aligned} |p-q|=|g(p)-g(q)| &=\left|g^{\prime}(\xi)\right||p-q| \\ & \leq k|p-q| \\ &<|p-q| \end{aligned}$
  which is a contradiction. >모순
• This contradiction must come from the only supposition, $p \neq q$.
• Hence, $p=q$ and the fixed point in $[a, b]$ is unique.

Mean Value Theorem

If $f \in C[a, b]$ and $f$ is differentiable on $(a, b)$, then a number $c$ exists such that

Motivating the Algorithm: An Example

A Single Nonlinear Equaton

Model Problem

Consider the quadratic equation:

Positive Root

The positive root of this equations is:

Single Nonlinear Equation $f(x)=x^2-x-1=0$

Fixed Point Formulation 1

Single Nonlinear Equation $f(x)=x^2-x-1=0$

One Possible Formulation for $g(x)$
Transpose the equation $f(x)=0$ for variable $x$ :

$x_{n+1}=g\left(x_n\right)=\sqrt{x_n+1}$ with $x_0=0$

$x_{n+1}=g\left(x_n\right)=\sqrt{x_n+1}$ with $x_0=0$

Rate of Convergence

We require that $\left|g^{\prime}(x)\right| \leq k<1$. Since
$g(x)=\sqrt{x+1}$ and $g^{\prime}(x)=\frac{1}{2 \sqrt{x+1}}>0$ for $x \geq 0$
we find that

Note

Fixed Point Formulation 2

Single Nonlinear Equation $f(x)=x^2-x-1=0$

A Second Formulation for $g(x)$

Transpose the equation $f(x)=0$ for variable $x$ :

x_{n+1}=g\left(x_n\right)=\frac{1}{x_n}+1 \text { with } x_0=1

$x_{n+1}=g\left(x_n\right)=\frac{1}{x_n}+1$ with $x_0=1$

Rate of Convergence

We require that $\left|g^{\prime}(x)\right| \leq k<1$. Since
$g(x)=\frac{1}{x}+1 \quad$ and $\quad g^{\prime}(x)=-\frac{1}{x^2}<0$ for $x$
we find that

Note

Functional (Fixed-Point) Iteration

Functional (Fixed-Point) Iteration

Now that we have established a condition for which $g(x)$ has a unique fixed point in I, there remains the problem of how to find it. The technique employed is known as fixed-point iteration.

이제 $g(x)$가 I에서 고유한 고정점을 갖는 조건을 설정했으므로, 그것을 찾는 방법에 대한 문제가 남아 있다. 사용된 기술은 고정점 반복으로 알려져 있다.

Basic Approach

• To approximate the fixed point of a function $g$, we choose an initial approximation $p_0$ and generate the sequence $\left\{p_n\right\}_{n=0}^{\infty}$ by letting $p_n=g\left(p_{n-1}\right)$, for each $n \geq 1$.

  함수 $g$의 고정점을 근사화하기 위해 초기 근사치 $p_0$을 선택하고 각 $n \geq 1$에 대해 $p_n=g\left(p_{n-1}\right)$를 허용하여 $\left\{p_n\right\}^{\infty}$ 시퀀스를 생성한다.

• If the sequence converges to $p$ and $g$ is continuous, then
  $p=\lim _{n \rightarrow \infty} p_n=\lim _{n \rightarrow \infty} g\left(p_{n-1}\right)=g\left(\lim _{n \rightarrow \infty} p_{n-1}\right)=g(p),$
  and a solution to $x=g(x)$ is obtained.

  만약 시퀀스가 $p$로 수렴하고 $g$가 연속이라면, $p=g(p)$이고
  그리고 $x=g(x)$에 대한 솔루션을 얻는다.

• This technique is called fixed-point, or functional iteration.

  이 기술을 고정점 또는 기능 반복이라고 한다.

Functional (Fixed-Point) Iteration

Fixed-Point Algorithm

To find the fixed point of $g$ in an interval $[a, b]$, given the equation $x=g(x)$ with an initial guess $p_0 \in[a, b]$ :
1. $n=1$;
2. $p_n=g\left(p_{n-1}\right)$;
3. If $\left|p_n-p_{n-1}\right|<\epsilon$ then 5 ;
4. $n \rightarrow n+1$; go to 2 .
5. End of Procedure.

A Single Nonlinear Equation

Example 1

The equation

has a unique root in [1,2]. Its value is approximately $1.365230013$.

$f(x)=x^3-4x^2-10=0$ on$[1,2]$

Possible Choices for $g(x)$

• There are many ways to change the equation to the fixed-point form $x=g(x)$ using simple algebraic manipulation.
• For example, to obtain the function $g$ described in part (c), we can manipulate the equation $x^3+4 x^2-10=0$ as follows:
  $4 x^2=10-x^3, \quad$ so $\quad x^2=\frac{1}{4}\left(10-x^3\right), \quad$ and $\quad x=\pm \frac{1}{2}\left(10-x^3\right)^{1 / 2}$
• We will consider 5 such rearrangements and, later in this section, provide a brief analysis as to why some do and some not converge to $p=1.365230013$.

5 Possible Transpositions to $x=g(x)$

Numberical Restults for $f(x)=x^3-4x^2-10=0$

Solving $f(x)=x^3+4 x^2-10=0$

$x=g(x)$ with $x_0=1.5$
$x=g_1(x)=x-x^3-4 x^2+10$ Does not Converge
$x=g_2(x)=\sqrt{\frac{10}{x}-4 x} \quad$ Does not Converge
$x=g_3(x)=\frac{1}{2} \sqrt{10-x^3}$
Converges after 31 Iterations
$x=g_4(x)=\sqrt{\frac{10}{4+x}}$
Converges after 12 Iterations
$x=g_5(x)=x-\frac{x^3+4 x^2-10}{3 x^2+8 x}$
Converges after 5 Iterations

Convergence Criteria for the Fixed-Point Method

Functional (Fixed-Point) Iteration

A Crucial Question

• How can we find a fixed-point problem that produces a sequence that reliably and rapidly converges to a solution to a given root-finding problem?
• The following theorem and its corollary give us some clues concerning the paths we should pursue and, perhaps more importantly, some we should reject.

Convergence Result

Let $g \in C[a, b]$ with $g(x) \in[a, b]$ for all $x \in[a, b]$. Let $g^{\prime}(x)$ exist on $(a, b)$ with

If $p_0$ is any point in $[a, b]$ then the sequence defined by

will converge to the unique fixed point $p$ in $[a, b]$.

Proof of the Convergence Result

• By the Uniquenes Theorem, a unique fixed point exists in $[a, b]$.
• Since $g$ maps $[a, b]$ into itself, the sequence $\left\{p_n\right\}_{n=0}^{\infty}$ is defined for all $n \geq 0$ and $p_n \in[a, b]$ for all $n$.
• Using the Mean Value Theorem $\left|g^{\prime}(x)\right| \leq k<1, \forall x \in[a, b]$, we write
  $\begin{aligned} \left|p_n-p\right| &=\left|g\left(p_{n-1}\right)-g(p)\right| \\ & \leq\left|g^{\prime}(\xi)\right|\left|p_{n-1}-p\right| \\ & \leq k\left|p_{n-1}-p\right| \end{aligned}$
  where $\xi \in(a, b)$

Mean Value Theorem

If $f \in C[a, b]$ and $f$ is differentiable on $(a, b)$, then a number $c$ exists such that

Functional (Fixed-Point) Iteration

Proof of the Convergence Result (Cont'd)

Applying the inequality of the hypothesis inductively gives

Since $k<1$

and $\left\{p_n\right\}_{n=0}^{\infty}$ converges to $p$.

Corrollary to the Convergence Result

If $g$ satisfies the hypothesis of the Theorem, then

Proof of Corollary

For $n \geq 1$, the procedure used in the proof of the theorem implies that

Thus, for $m>n \geq 1$,

However, since $\lim _{m \rightarrow \infty} p_m=p$, we obtain

Example: $g(x)=g(x)=3^{-x}$

Consider the iteration function $g(x)=3^{-x}$ over the interval $\left[\frac{1}{3}, 1\right]$ starting with $p_0=\frac{1}{3}$. Determine a lower bound for the number of iterations $n$ required so that $\left|p_n-p\right|<10^{-5}$ ?

Determine the Parameters of the Problem

Note that $p_1=g\left(p_0\right)=3^{-\frac{1}{3}}=0.6933612$ and, since $g^{\prime}(x)=-3^{-x} \ln 3$, we obtain the bound

Use the Corollary

Therefore, we have

We require that

Footnote on the Estimate Obtained

• It is important to realise that the estimate for the number of iterations required given by the theorem is an upper bound.
• In the previous example, only 21 iterations are required in practice, i.e. $p_{21}=0.54781$ is accurate to $10^{-5}$.
• The reason, in this case, is that we used
  $g^{\prime}(1)=0.762$
  whereas
  $g^{\prime}(0.54781)=0.602$
• If one had used $k=0.602$ (were it available) to compute the bound, one would obtain $N=23$ which is a more accurate estimate.

Example

Sample Problem $f(x)=x^3+4 x^2-10=0$

Trying myself.