WYKŁAD 1 04.10.2002

Prof. Ewa Majchrzak

LITERATURA:

E.Majchrzak, B. Mochnacki, Metody Numeryczne. Podstawy teoretyczne, aspekty praktyczne i algorytmy, Wyd. Politechniki Śląskiej, Gliwice, 1994, 96, 98

ZAGADNIENIA:

1. INTERPOLACJA (6h)

2. CAŁKOWANIE NUMERYCZNE (4h)

3. APROKSYMACJA FUNKCJI (2h)

4. METODY ROZWIĄZYWANIA RÓNAŃ ALGEBRAICZNYCH (2h)

5. METODY ROZWIĄZYWANIA UKŁADÓ RÓWNAŃ (6h)

6. METODY ROZWIĄZYWANIA RÓWNAŃ RÓŻNICZKOWYCH ZWYCZAJNYCH, METODY EULERA (2h)

7. METODY ROZWIĄZYWANIA RÓWNAŃ RÓŻNICZKOWYCH CZĄSTKOWYCH (…)

INTERPOLACJA

FUNKCJI JEDNEJ ZMIENNEJ

Def. Dany jest zbiór punktów (x₀, y₀), (x₁, y₁), (x₂, y₂), …, (x_n, y_n) - n+1 punktów.

Celem interpolacji jest znalezienie funkcji W(x), która spełnia warunek:

W(x_i) = y_i, i=0, 1, 2,…, n

wartość funkcji W w punktach x_i dla i=0, 1, ,2 …, n (n+1 przypadków) musi być równa y_i.

Interpretacja geometryczna:

Szukamy funkcji, która przechodzi przez punkty x₀, x₁, x₂, …, x_n.

W(x) - wielomian interpolacyjny

(x_i, y_i) - węzły interpolacji

Funkcje
- funkcje bazowe (znane) - muszą być znane w poszczególnych przypadkach interpolacji

Wyznaczamy:

a₀, a₁, a₂, …, a_n - współczynniki

Zapis macierzowy:

- elementami macierzy są funkcje (macierz jednowierszowa)

- (wektor)

- mnożenie macierzy

Z warunku interpolacji otrzymamy następujące równania:

…

Możemy wyznaczyć a₀, a₁, a₂, …, a_n - mamy układ n+1 równań z n+1 niewiadomymi

X A Y

X - macierz główna

A - wektor niewiadomych

Y - wektor wartości

UWAGA: Macierz główna tego układu w wierszach zawiera wartości funkcji bazowych w kolejnych węzłach interpolacji

XA = Y

Jeśli wyznacznik macierzy X jest różny od zera:
- współczynniki x-owe muszą być różne między sobą:
, możemy wówczas wyznaczyć wartości współczynników a₀, a₁, a₂, …, a­_n:

A = X^-1Y

INTERPOLACJA „NATURALNA” - za pomocą wielomianu w postaci naturalnej

Dany jest zbiór punktów (x₀, y₀), (x₁, y₁), (x₂, y₂), …, (x_n, y_n).

(podanie funkcji bazowych wystarcza, aby stosować poszczególne odmiany interpolacji)

macierz pełna

UWAGA: W interpolacji naturalnej macierz główna jest macierzą pełną, tzn.
(jest to zjawisko niekorzystne)

Przykład:

Napisać układ równań, z którego wyznaczamy współczynniki wielomianu naturalnego:

Dla węzłów:

1. (1,3), (2,7), (4,1)

2. (2,0), (3,7), (-1,4), (9,3)

ad. a) n = 2 (bo punkty liczymy od 0)

W(x) = a₀ + a₁x + a₂x² (wielomian stopnia drugiego)

1 x x²

ad. b) n = 3

W(x) = a₀ + a₁x + a₂x² + a₃x³

WYKŁAD 2 11.10.2002

INTERPOLACJA LAGRANGE'A

Def. Dany jest zbiór punktów (x₀, y₀), (x₁, y₁), (x₂, y₂), …, (x_n, y_n­)

Wielomian interpolacyjny:

→ wielomian stopnia n

Założenie interpolacji:

np. n = 2 (3 węzły)

(x₀, y₀), (x₁, y₁), (x₂, y₂)

Przykład:

Dany jest zbiór punktów:

1. (0, 3), (2, -1), (4, 1)

2. (1, 4), (2, 5), (3, 7), (5, 4)

3. (1, 3), (4, 2)

Napisać wielomian interpolacyjny Lagrange'a.

ad. a) n = 2

ad. b) n = 3

ad. c) n = 1

Załóżmy, że węzły interpolacji są węzłami równoodległymi

Dany jest zbiór punktów (x₀, y₀), (x₁, y₁), …, (x_n, y_n), przy czym x_i+1 - x_i = h = const

RÓŻNICE SKOŃCZONE (definicja rekurencyjna)

Def.
(różnica skończona rzędu pierwszego)

(różnica skończona rzędu drugiego)

(różnica skończona rzędu n-tego)

np.

TABLICE RÓŻNIC SKOŃCZONYCH (NEWTONA)

xi	yi				…
					…

↓

(kolumna opcjonalna)

- I wzór interpolacyjny Newtona

- II wzór interpolacyjny Newtona

Przykład:

Dany jest zbiór punktów: (0,1), (0.1,2), (0.2,-1), (0.3,5), (0.4,-2), (0.5,1)

Utworzyć tablicę różnic skończonych.

n = 5

xi	yi
0	1	1	-4	13	-35	80
0.1	2	-3	9	-22	45
0.2	-1	6	-13	23
0.3	5	-7	10
0.4	-2	3
0.5	1

I WZÓR INTERPOLACYJNY NEWTONA

Dany jest zbiór punktów (x₀, y₀), (x₁, y₁), (x₂, y₂), …, (x_n, y_n), przy czym h = x_i+1 - x_i = const

x = x₀: q = 0

x = x₁:

x = x₂:

x = x_n:

a₀ = y₀ (z I równania)

a₀ + a₁ = y₁ → y₀ + a₁ = y₁ → a₁ = y₁ - y₀ =

a₀ + 2a₁ + 2a­₂ = y₂ → y₀ + 2
+ 2a₂ = y₂ → 2a₂ = y₂ - 2
- y₀ →
→

I WZÓR INTERPOLACYJNY NEWTONA

WYKŁAD 3 18.10.2002

II WZÓR INTERPOLACYJNY NEWTONA

Def. Dany jest zbiór punktów (x₀, y₀), (x₁, y₁), …, (x_n, y_n)

h = x_i+1 - x_i = const

Obliczyć ile wynosi q:

x = x₀: q = - n

x = x₁: q = - (n - 1)

x = x_n: q = 0

Przeprowadzamy analogiczne rozważania jak przy I wzorze Newtona (i nie tylko)

II WZÓR INTERPOLACYJNY NEWTONA:

dla

Przykład

Dany jest zbiór punktów:

1. (0,2), (0.1,3), (0.2,5), (0.3,4)

2. (0,1), (0.5,3), (1,2), (1.5,4), (2,6)

Napisać I i II wzór interpolacyjny Newtona. W przykładzie a) ograniczyć się do 3 składników tych wzorów.

1. Tworzymy tablicę różnic skończonych:

xi	yi
0	2	1	1	-4
0.1	3	2	-3
0.2	5	-1
0.3	4

I wzór interpolacyjny Newtona:

II wzór interpolacyjny Newtona:

INTERPOLACJA CZEBYSZEWA:

Def. Dany jest zbiór punktów (x₀, y₀), (x₁, y₁), …, (x_n, y_n), przy czym

(doczytać jak „zaciskać przedział za pomocą wzoru Czebyszewa z (a,b) do [-1,2])

Wielomian Czebyszewa:

, k=1, 2, …

np.

Wielomiany Czebyszewa są funkcjami bazowymi w interpolacji Czebyszewa.

i = 0, 1, 2, …, n

W tym rodzaju interpolacji należy do końca rozwiązać układ równań.

Przykład

Napisać układ równań, z którego wyznaczamy współczynniki wielomianu Czebyszewa dla następujących punktów:

1. (-0.5, 0), (0,5), (1,2)

2. (-1,2), (-
   ,3), (0,2), (1,4)

ad. a) n = 2

1 x 2x² - 1

a₀, a₁, a₂

INTERPOLACJA TRYGONOMETRYCZNA

Def. Dany jest zbiór punktów (x₀, y₀), (x₁, y₁), …, (x_2n, y_2n)

Przykład

Napisać układ równań, z którego wyznaczymy współczynniki wielomianu trygonometrycznego dla następujących punktów:

1. (
   ,1), (0,2), (
   ,3), (
   , 1), (
   ,4)

2. (0,2), (
   ,3), (
   ,-1)

cos x sin x

a₀, a₁, a₂

WYKŁAD 4 08.11.2002

CAŁKOWANIE NUMERYCZNE

, f(x) ciągła i ograniczona w [a,b]

KWADRATURY INTERPOLACYJNE

Przedział [a,b] dzielimy na n równych podprzedziałów.

, przy czym

Uwaga!!! F(x) zastępujemy I wzorem interpolacyjnym Newtona:

- metoda prostokątów

- metoda trapezów

- metoda Simpsona

METODA PROSTOKĄTÓW

METODA TRAPEZÓW

METODA SIMPSONA

Przedział [a,b] dzielimy na parzystą liczbę podprzedziałów.

n - parzyste

KWADRATURY GAUSSA

, f(x) ciągła i ograniczona w [a,b]

I ETAP:

Sprowadzenie całki do całki

Podstawienie:

	- 1	1
x	a	B

WE: f(x); a, b;

I ETAP:

Przykład: Sprowadzić całkę
do całki znormalizowanej.

a = 2

b = 4

II ETAP:

n - liczba punktów Gaussa (n = 1, 2, 3, …, 12) - ustalamy sami

- współrzędne punktów Gaussa (z tablic)

W_i - wagi punktów Gaussa (z tablic)

(współrzędne i wagi podawane są z dokładnością do 15 miejsc po przecinku)

n		Wi
2	-0.57735 0.57735	1 1
3	-0.77459 0 0.77459	0.55555 0.88888 0.55555
4	-0.86113 -0.33998 0.33998 0.86113	0.34785 0.65214 0.65214 0.34785
5	…

Przykład dla n = 3: (dokładność 2)

METODA MONTE CARLO

,

n - liczba strzałów w tarczę

k - liczba strzałów pod krzywą

WYKŁAD 5 15.11.2002

KUBERTURY GAUSSA

, gdzie f(x,y) - ciągła i ograniczona w D (D - trójkąt, obszar opisany współrzędnymi wierzchołków)

I etap:

x₀,y₀

x₂,y₂

x₁,y₁

0,1

0,0

1,0

→ trójkąt znormalizowany

Podstawienie:

		x	y
0	0	x1	y1
1	0	x2	y2
0	1	x3	y3

Przykład:

, D: (2,1), (3,7), (1,1)

P:

II etap:

n - liczba punktów Gaussa (dobieramy sami): dla n = 1,3,5,7

- współrzędne punktów Gaussa

w_i - wagi punktów Gaussa z tablic

n			wi
1			1
3	0	0

Przykład: (n = 3)

CAŁKOWANIE PO CZWOROKĄCIE

, f(x,y) - ciągła i ograniczona w D

I etap:

D: (x₁,y₁), (x₂,y₂), (x₃,y₃), (x₄,y₄)

Y x₃,y₃

x₂,y₂

D

x₄,y₄

x₁,y₁

X

1

-1 1

-1

Podstawienie:

		x	y
-1	-1	x1	y1
1	-1	x2	y2
1	1	x3	y3
-1	1	x4	y4

II etap:

n - liczba punktów Gaussa (ustalamy sami)

- współrzędne punktów Gaussa z tablic dla

w_i, w_j - wagi punktów Gaussa kwadratów Gaussa

np. n = 2

n	,	wi,j
2	-0.57	1
		0.57	1

Metody numeryczne - wykłady

20

---