Iranian student olimpyad

[myra_panama]

Let the function $f(x)$ be four times continuously differentiable and have a simple zero $\alpha$ . Successive approximations $x_n$ , n=1,2,... to $\alpha$ are computed from
$x_{n+1}=\frac12(x'_{n+1}+x''_{n+1})$ , where
$x'_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$
$x''_{n+1}=x_n-\frac{g(x_n)}{g'(x_n)}$ , $g(x)=\frac{f(x)}{f'(x)}$
Prove that if sequence {$x_n$} converges to $\alpha$ , then the rate of convergence to cubic. (25-points)

[myra_panama]

is there any idea???

ну если подставить выражении $x'_{n+1} , x''_{n+1}$ , то получим:
$x_{n+1}-x_n=-\frac12[\frac{2f'(x_n)-\frac{f(x_n)f''(x_n)}{f'(x_n)}}{\frac{f'(x_n)}{f(x_n)}-\frac{f''(x_n)}{f'(x_n)}}]$.....

-- Сб июн 18, 2011 09:59:30 --

Prove that if sequence {$x_n$} converges to $\alpha$ , then the rate of convergence is cubic.

[TOTAL]

myra_panama в сообщении #459372 писал(а):

если подставить выражении $x'_{n+1} , x''_{n+1}$ , то получим:
$x_{n+1}-x_n=-\frac12[\frac{2f'(x_n)-\frac{f(x_n)f''(x_n)}{f'(x_n)}}{\frac{f'(x_n)}{f(x_n)}-\frac{f''(x_n)}{f'(x_n)}}]$.....

Получать надо неравенство $|x_{n+1}- \alpha| \le M|x_{n}- \alpha|^3$

[myra_panama]

TOTAL в сообщении #459399 писал(а):

Получать надо неравенство $|x_{n+1}- \alpha| \le M|x_{n}- \alpha|^3$

как , откуда , почему , объясните пожалуйста??

[TOTAL]

Запишите итерационный процесс в виде

$$x_{n+1} = \varphi(x_n),$$

где

$$\varphi(x)= x - \frac{1}{2} \left( \frac{f(x)}{f'(x)} + \frac{g(x)}{g'(x)} \right)$$

Покажите, что

$$\varphi'(\alpha)=\varphi''(\alpha)=0$$

Третий порядок метода следует из

$$\varphi(x_n)=\varphi(\alpha)+(x_n - \alpha)\varphi'(\alpha) + \frac{(x_n - \alpha)^2}{2}\varphi''(\alpha) + O\left( (x_n - \alpha)^3 \right)$$

[myra_panama]

TOTAL , спасибо за указание.. все понял... будем дальше решать...

2.Consider the following iteration formula for estimating $A^{-1}$ of $n\times n$ symmetric positive definite matrix $A$,
$X_{n+1}=X_n+q(AX_n-I)$ ($*$)

where $q$ is a constant and $I$ is the $n\times n$ identity matrix.
(i) Under what conditions on $q $ the iteration formula ($*$) converges to $A^{-1}$.
(ii)What should the value of $q$ be so that the convergence is a fast as possible?

[ewert]

myra_panama в сообщении #460119 писал(а):

(i) Under what conditions on $q $ the iteration formula ($*$) converges to $A^{-1}$.
(ii)What should the value of $q$ be so that the convergence is a fast as possible?

$X_{n+1}=B\,X_n-q\,I$, где $B=I+q\,A$. Последнее слагаемое $(-q\,I)$ для сходимости не имеет значения, а условием сходимости будет $q<0$ и $1+q\lambda_{\min}>-1$, где $\lambda_{\min}$ -- наименьшее собственное число матрицы $A$. Наибольшая скорость достигается при $1+q\lambda_{\min}=-(1+q\lambda_{\max})$. Задача ни разу не олимпиадная.

[myra_panama]

ewert в сообщении #460131 писал(а):

Задача ни разу не олимпиадная.

Ну да , простая задачка ,.,, но это было в международной олимпиаде для студентов в Иране

[ewert]

myra_panama в сообщении #460133 писал(а):

но это было в международной олимпиаде для студентов в Иране

Она нелепа как олимпиадная. Если человек хоть сколько-то знаком с итерационными методами, то он ответит мгновенно. А если не знаком, то просто не поймёт, о чём речь.

[myra_panama]

идем дальше...

3. Consider the following quadrature rule
$\int\limits_{0}^{3h}f(x)dx\approx a_1f(0)+a_2f(2h)+a_3f(3h)$ ($*$)
(i) Find $a_1,a_2,a_3$ such that the rule has highest order (or degree) of precision
(ii) Write the composite rule of ($*$) for $\int\limits_a^b f(x)dx $ with
$h=\frac{b-a}{3h} , x_i=a+ih , i=0,1,...,3n$
(iii)Which one of following integrals can be approximated by the composite rule of ($*$) ?
a)$\int\limits_0^1\frac{\tg x}{\sqrt{1-x}}dx ,$
b)$\int\limits_{-1}^1\frac{\cos x}{\sqrt{1-x^2}}dx$
c)$\int\limits_0^1\frac{\cos x}{\sqrt x}$

(Оффтоп)

Я с начало сделал замену $f(x)=a_0+a_1x+a_2x^2+\cdots$
и с легкостью нашел коэффициенты , но с (ii) как то не получается

[myra_panama]

4.(i) The iteration defined by $x_{k+1}=\frac12(x^2_k+c)$ , where $0<c<1$, has two fixed points $\xi_1 , \xi_2$ , where $0<\xi_1<1<\xi_2$ . Show that

$$x_{k+1}-\xi_1=\frac12(x_k+\xi_1)(x_k-\xi_1) , k=0,1,2,...$$

and deduce that $\lim\limits_{k\to\infty}x_k=\xi_1$ , if $0\le x_0<\xi_2$.
(ii) How does the iteration behave for other values of $x_0$

[myra_panama]

Опечатка
3.(ii) Write the composite rule of ($*$) for $\int\limits_a^b f(x)dx $ with
$h=\frac{b-a}{3n} , x_i=a+ih , i=0,1,...,3n$

[myra_panama]

5.Let $I=[0,1]$ and $ X=C^1(I)$ be the space of all continuously differentiable real valued functions on I. Let $\lVert f\rVert_{\infty}=\sup\limits_{x\in I}\lvert f(x)\rvert$ for $f\in X$ and define three metrics on X as follows:
$\[ d_{0}(f,g)=\lVert f-g\rVert_{\infty},\ d_{1}(f,g)=\lvert f(0)-g(0)\rvert+\lVert f'-g'\rVert_{\infty}\text{ and }d_{2}(f,g)=\lVert f-g\rVert_{\infty}+\lVert f'-g'\rVert_{\infty}, \]$
for $f,g\in X$
(i) (9 points) Is $(X,d_0)$ a complete metric space? Why?
(ii) (8 points) Is $(X,d_1)$ a complete metric space? Why?
(iii) (5 points) Show that $(X,d_2)$ is a complete metric space.
(iv) (8 points) Are the metrics $d_1$ and $d_2 $equivalent on X? Why?

[ewert]

myra_panama в сообщении #460660 писал(а):

(i) (9 points) Is $(X,d_0)$ a complete metric space? Why?

Правильный ответ: потому. Типа читайте учебники.

myra_panama в сообщении #460660 писал(а):

(iii) (5 points) Show that $(X,d_2)$ is a complete metric space.

Аналогично: читайте теоремы вложения.

Снова стандартные факты, даже без какого-то намёка на олимпиадность. Но меня удивили эти пойнты. Там что: чем проще задача, тем больше за неё дают баллов?...

[myra_panama]

ewert в сообщении #460679 писал(а):

Снова стандартные факты, даже без какого-то намёка на олимпиадность. Но меня удивили эти пойнты. Там что: чем проще задача, тем больше за неё дают баллов?...

ну хорошо , это не моя проблема ....
Но к сожалению я уже начал изучать функанализ ... Давайте помогите разобраться с последний задачкой..
Метрическое пространство M есть множество точек с фиксированной функцией расстояния (также называется метрикой) $d:M \times M \to R$ . И должна выполнятся следующие условии:
1) $d(x,y)=0 \Leftrightarrow x=y$
2) $d(x,y)=d(y,x)$
3) $d(x,z)\le d(x,y) + d(y,z)$
Любое нормированное пространство можно превратить в метрическое, определив функцию расстояния $d(x,\;y)=\|y-x\|.$

-- Вт июн 21, 2011 14:23:05 --

и еще.. , что здесь символизирует $\infty$ в $\lVert f\rVert_{\infty}$