Användare:Bjorne/LANA

Denna sida innehåller saker som jag tycker kan vara bra att ha nedskrivna och som är smidiga att ha på en wiki.

Iterativa metoder

Allmänt: <math> \lim_{k \to \infty} \frac{|x_{k+1} - x^*|}{|x_k - x^*|^q} = C < \infty</math>. <math>q</math> kallas konvergensordning och <math>C</math> kallas asymptotisk felkonstant.

Intervallhalvering

Välj två startvärden med kravet <math>{f(a) \over f(b)} < 0</math>, d.v.s. <math>f</math> har olika tecken i de olika punkterna.

while ((b - a) > tol) do
 m = a + (b - a)/2
 if sign(f(a)) = sign(f(m)) then
  a = m
 else
  b = m
 end
end

Fixpunktsiteration

Iterativa algoritmer på formen <math>x_{k+1} = g(x_k)</math> kallas fixpunktsiterationer eller funktionsiterationer. Konvergerar för <math>|g'(x)| < 1</math>, med linjär konvergenshastighet. För <math>|g'(x)| = 0</math>, kvadratisk. Divergens annars.

Newtons metod

En variabel

Newtons metod:

<math>x_{k+1} = x_k - {f(x_k) \over f'(x_k)}</math>

Newtons metod har kvadratisk konvergens för enkelrötter resp. linjär för multipelrötter.

Flera variabler

<math>\mathbf{x}_{k+1} = \mathbf{x}_k + \mathbf{s}_k, \quad \mathbf{J}(\mathbf{x}_k)\mathbf{s}_k = - \mathbf{f}(\mathbf{x}_k)</math>

Lokalt konvergent. Kvadratisk konvergensordning vid reguljär rot. Dämpad; lägg till <math>\alpha_k</math> som koefficient framför <math>\mathbf{s}_k</math> i första högerledet, <math>\alpha_k</math> kallas steglängd.

Finns kvasi-Newton, i syfte att slippa beräkna Jacobianen. Man ersätter den med approximation <math>\mathbf{B}_k</math>.

Sekantmetoden

<math>x_{k+1} = x_k - {f(x_k)(x_k - x_{k-1}) \over \left( f(x_k) - f(x_{k-1}) \right)}</math>

Konvergerar superlinjärt, dvs <math>1 < r \approx 1.618 < 2</math>

Ofta mer effektiv än Newtons metod.

ODE

Det finns enstegs- och tvåstegsmetoder. Man använder testproblemet:

<math>\begin{cases}y' = \lambda y \\ y(0) = y_0\end{cases}</math>

denna har exakt lösning <math>y(t) = y_0 \exp{\lambda t}</math>, osv. Om <math>\Re(\lambda) \le 0</math> är metoden stabil.

Euler

Framåt

<math>y_{k+1} = y_k + h \cdot f(t_k, y_k)</math>

Bakåt

<math>y_{k+1} = y_k + h \cdot f(t_{k+1}, y_{k+1})</math>

Mittpunktsmetoden

<math>y_{k+1} = y_{k-1} + 2hf(t_k, y_k)</math>

Trapetsmetoden

<math>y_{k+1} = y_k + {h \over 2} ( f(t_k, y_k) + f(t_{k+1}, y_{k+1}))</math>