Karta wzorów Metody Numeryczne

• Zapis stałopozycyjny

• Zapis zmiennopozycyjny

• Algorytm Herona

• Algorytm Hornera

• Interpolacja wielomianowa przez układ równań

• Interpolacja wielomianowa metodą Newtona Wn(x) = f (x0) + f [x0; x1]ω0(x) + · · · + f [x0; · · · ; xn]ωn−1

ωi(x) = (x − x0) · · · (x − xi) f [xi; xi+1; · · · ; xi+n] = f[xi+1;··· ;xi+n]−f[xi;xi+1;··· ;xi+n−1]

xi+n−xi

• Interpolacja wielomianowa metodą Lagrange’a n

Y

x − xj

pi(x)

=

xi − xj

j=0,j6=i

(x − x0)(x − x1) · · · (x − xi−1)(x − xi+1) · · · (x − xn)

=

.

(xi − x0)(xi − x1) · · · (xi − xi−1)(xi − xi+1) · · · (xi − xn) n

X

Ln(x) =

pi(x) · yi.

i=0

• Interpolacja trygonometryczna

– Dla nieparzystej ilości (n) punktów węzłowych m = n−1

2

T (x) = a0 + Pm [a

2

k=1

k · cos(k · x) + bk · sin(k · x)]

– Dla parzystej ilości (n) punktów węzłowych m = n 2

T (x) = a0 + Pm−1[a

· cos(m · x)

2

k=1

k · cos(k · x) + bk · sin(k · x)] + am 2

– Dla obu powyższych przypadków: n−1

2 X

aj

=

[f (xk) · cos(k · xj)]

n k=0

n−1

2 X

bj

=

[f (xk) · sin(k · xj)]

n k=0

• Aproksymacja średniokwadratowa wielomianowa Układ k + 1 równań liniowych, względem współczynników a0,a1, a2, · · · , ak: n

n

n

n

n

X

X

X

X

X

a0

xm + a

x1+m + a

x2+m + · · · + a

xk+m =

y

i

1

i

2

i

m

i

ixm

i

i=0

i=0

i=0

i=0

i=0

dla m = 0, 1, 2, · · · , k.

• Metoda Aitkena

y

i

xi − x

yj

xj − x

W

i,j (x) =

xj −xi

1

W

i,j (x)

xj − x

Wi,k

xk − x

W

i,j,k (x) =

xk−xj

W

1,2,..k−1,k (x)

xk − x

W1,2,...,k−1,m(x)

xm − x

W

1,2,..,k,m =

xm−xk

• Rodziny wielomianów ortogonalnych

• Eliminacja Gaussa

• Eliminacja Gaussa-Jordana

• Rozkład LU metodą Doolittle’a dla wszystkich i ∈ {1, 2, . . . , n}: uij = aij − Pi−1 l

k=1 ik ukj

dla

j ∈ {i, i + 1, . . . , n};

lji = 1

a

l

dla

j ∈ {i + 1, i + 2, . . . , n}.

u

ji − Pi−1

jk uki

ii

k=1

• Rozkład Cholesky’ego-Banachiewicza r

lii =

aii − Pi−1 l2

k=1 ik

a

l

l

ji −Pi−1

k=1 jk lik

ji =

lii

• Rozkład RT

k−1

X

~

rk = ~ak −

tik~ri

i=1

(~ak, ~ri)

tik = (~ri,~ri)

• Metoda Jacobiego

~

x(k+1) = D−1 −(L + U )~

x(k) + ~b ,

(k+1)

(k)

(k)

x

= 1

b

a

− Pn

a

, i = 1, 2, . . . , n.

i

a

i − Pi−1

ij x

ij x

ii

j=1

j

j=i+1

j

• Metoda Gaussa-Seidla

−

~

x(k+1) = (D + L) 1 −U ~

x(k) + ~b ,

(k+1)

(k+1)

(k)

x

= 1

b

a

− Pn

a

, i = 1, 2, . . . , n.

i

a

i − Pi−1

ij x

ij x

ii

j=1

j

j=i+1

j

• Metoda stycznych (Newtona) f (xk)

xk+1 = xk −

k = 1, 2, . . .

f 0(xk)

• Metoda siecznych

f (xk)(xk − xk−1)

xk+1 = xk −

k = 1, 2, . . .

f (xk) − f (xk−1)

• reguła falsi

xk − a

xk+1 = xk −

f (xk)

k = 1, 2, . . .

f (xk) − f (a)

2

• metoda Steffensena f (xk)

xk+1 = xk −

f (xk)

k = 1, 2, . . .

f (xk + f (xk)) − f (xk)

• Wielowymiarowa metoda stycznych (Newtona)

−

~

x

1 ~

k+1 = ~

xk − (J(~xk))

f (~

xk),

gdzie J to macierz Jacobiego

 ∂f1

∂f 

· · ·

1

∂x

∂x



1

n 

.

.

J = 

.

. .

.





.

.

.







 ∂fm

∂f 

· · ·

m

∂x1

∂xn

• Ogólny wzór kwadratur

b

ˆ

n

X

f (x)dx ≈

f (xi) · Ai

a

i=0

• Wzór na współczynniki interpolacyjnych kwadratur Newtona-Cotesa ˆ n Y t − j

Ai = h

dt

0

i − j

j=0,j6=i

• Korzystanie z wielomianów ortogonalnych.

• Całka metodą Monte-Carlo korzystającą ze średniej wartości funkcji jednej zmiennej ˆ b

n

b − a X

f (x)dx ≈ (b − a) · fsr =

f (zi)

a

n

i=1

gdzie zn = a + (b − a) · xn.

• Całka metodą Monte-Carlo korzystającą ze średniej wartości funkcji wielu zmiennych i oszacowanie błędu całki

ˆ

r < f2 > − < f >2

f dV ≈ V < f > ±V

n

3