Egzamin z Obliczeń Naukowych, 05.06.2000. (3 godz.)

1. Niech $F:R^N\rightarrow R^N$ spełnia założenia standardowe, w szczególności - ma miejsce zerowe w $x^*\in R^N$. Rozważmy metodę iteracyjną, której jeden krok składa się z kroku metody Newtona i kroku metody cięciw, tzn. jeśli $x_n$ są iteracjami naszej metody, to $x_{n+1}$ oblicza się na podstawie $x_n$ według wzoru:
   $$\begin{eqnarray*} z &=& x_n - F'(x_n)^{-1}\cdot F(x_n),\\ x_{n+1} &=& z - F'(x_n)^{-1}\cdot F(z). \end{eqnarray*}$$
   
   
   
   
   
   
   1. (2 pkt) Wykaż, że istnieje $\delta > 0$ takie, że jeśli $x_0\in \mathcal{B}(\delta)$, to także $x_n\in \mathcal{B}(\delta), \quad \forall n$.

   2. (2 pkt) Wykaż, że istnieje $\delta^* > 0$ takie, że jeśli $x_0\in \mathcal{B}(\delta^*)$, to $x_n\rightarrow x^*$ superliniowo; podaj wykładnik zbieżności.

   3. (1 pkt) Porównaj własności (rząd zbieżności, koszt) rozważanej metody z metodą, w której w jednym kroku po prostu wykonujemy dwie iteracje Newtona.

2. Niech $F:R^N\rightarrow R^N$ ma miejsce zerowe w $x^*\in R^N$. Przypuśćmy ponadto, że $F$ jest różniczkowalna w $R^N$, a jej pochodna $F': R^N \rightarrow R^{N\times N}$ jest ciągła. O macierzy pochodnej $F'(x)$ wiemy, że jest symetryczna, a ponadto istnieją stałe $0< m \leq M$ (niezależne od $x$) takie, że wartości własne $F'(x)$ spełniają

   
   

   $$0 < m \leq \lambda_i(x) \leq M, \quad \forall i=1,\ldots,N, \quad \forall x\in R^N.$$
   
   
   1. (3 pkt) Znajdź zakres parametru $\tau\in R$, dla którego nieliniowa metoda Richardsona:

      
      

      $$x_{n+1} = x_n - \tau\cdot F(x_n)$$
      
      

      jest zbieżna do $x^*$ w normie Euklidesowej $\vert\vert\cdot\vert\vert _2$.

   2. (1 pkt) Jaki jest wykładnik zbieżności tej metody?

   3. (1 pkt) Jaką wartość parametru relaksacyjnego $\tau$ polecić jako ``optymalną'' dla tej metody?

3. (3 pkt) Sformułuj prawo Amdahla i podaj wnioski, które zeń płyną.

4. (3 pkt) Wyjaśnij, co to jest preconditioning, kiedy się go stosuje i dlaczego. Podaj przykład prostego preconditionera i krótko opisz jego wady i zalety.

Oceny: 8..10 pkt - dst, 11..13 pkt - db, 14..16 pkt - bdb.
P O W O D Z E N I A !

Egzamin poprawkowy z Obliczeń Naukowych, 11.09.2000. (3 godz.)

1. (5 pkt) Niech $x^*$ będzie zerem funkcji $F:R^N\rightarrow R^N$, która spełnia standardowe założenia. Rozważmy hipotetyczną metodę iteracyjną

   
   

   $$x_{n+1} = x_n - F'(x^*)^{-1}\cdot F(x_n).$$
   
   

   Dla jakich $\delta > 0$ spełniony będzie warunek, że jeśli $x_0\in \mathcal{B}(\delta)$, to także $x_{n}\in \mathcal{B}(\delta), \quad \forall n$? Dlaczego jest to ``hipotetyczna'' metoda? Przeanalizuj szybkość zbieżności i koszt jednego kroku tej metody; porównaj z metodami: Newtona i cięciw.

2. (5 pkt) Udowodnić, że jeśli macierz $A$ jest silnie diagonalnie dominująca,
   
   $$\vert a_{ii}\vert> \sum_{j\neq i}\vert a_{ij}\vert> 0,$$
   
   
   to metoda Jacobiego jest zbieżna w normie $\vert\vert\cdot\vert\vert _\infty$. Ponadto, macierz $A$ jest wtedy nieosobliwa.

3. (3 pkt) Dysponujemy równoległym algorytmem wyceny opcji giełdowych, który może działać na $p$ procesorach, a jego ostatecznym celem jest podawanie wyników w ciągu 2-3 minut. Na jednym procesorze, nasz program daje niestety wynik w ciągu 36 minut. Podczas testów okazało się ponadto, że na 4 procesorach program dał wynik po 10 minutach. Posługując się równoległym prawem Amdahla, poprzyj bądź zakwestionuj decyzję zakupu 16-procesorowej maszyny w celu uzyskania pożądanej szybkości działania naszego programu.

4. (3 pkt) Podaj przykład dwóch (matematycznie równoważnych) algorytmów numerycznych, z których jeden źle, a drugi dobrze wykorzystuje hierarchię pamięci współczesnego komputera.

Oceny: 8..10 pkt - dst, 11..13 pkt - db, 14..16 pkt - bdb.
P O W O D Z E N I A !

Ta strona została stworzona na podstawie pliku w formacie LaTeX2e przy użyciu konwertera Latex2HTML