1

Przegląd zagadnień informatyki



metody numeryczne



przetwarzanie tekstów



bazy danych



grafika komputerowa



sztuczna inteligencja



symulacja



telekomunikacja



języki programowania



systemy operacyjne

Metody numeryczne



układy równań liniowych



(układy) równań nieliniowych



(układy) równań różniczkowych

(

y)

y



całkowanie numeryczne



optymalizacja (poszukiwanie minimum)



interpolacja i aproksymacja

Układy równań liniowych



W ekonomii technice astronomii występują

















10

2

4

14

5

3

y

x

y

x

np.



W ekonomii, technice, astronomii występują
układy nawet kilkuset równań z kilkuset
niewiadomymi.



Układ o 10 niewiadomych przekracza siły
przeciętnego rachmistrza.

Układy równań liniowych

Metody rozwiązywania



metoda eliminacji (Gauss)



metody Gaussa-Seidela i SOR



metoda Grama-Schmidta (dla układów

(

nadokreślonych)

Układy równań nieliniowych

Równania

x + ln x = 0

nie można rozwiązać

analitycznie. Musimy stosować metody
przybliżone:



Metoda podziału połówkowego (bisekcji)



Metoda podziału połówkowego (bisekcji).



Metoda Newtona (stycznych).

Metoda bisekcji

Służy do rozwiązywania równań postaci

f(x) = 0

Wymagane jest, aby funkcja na końcach

y

g

j

,

y

j

pewnego, danego przedziału miała przeciwne
znaki. Ponadto f(x) musi być ciągła.

2

Metoda bisekcji

Metoda bisekcji

Metoda Newtona



Wymaga obliczenia nie tylko samej funkcji
f(x), ale także jej pochodnej f'(x); jest za to
kilkakrotnie szybsza.



Znajomość pochodnej potrzebna jest do
poprowadzenia stycznej do wykresu.



Metoda działa także wtedy, gdy f jest funkcją
wielu zmiennych.



Niekiedy metoda Newtona zawodzi; musimy
wtedy stosować metodę bisekcji.

Metoda Newtona

Metoda Newtona

Metoda Newtona

Metoda Newtona

Metoda Newtona

Metoda Newtona

Metoda Newtona

Metoda Newtona -- problemy

problemy

x

0

x

1

3

Metoda Newtona

Metoda Newtona -- problemy (2)

problemy (2)

Równania różniczkowe



R.r. spotykamy w wielu naukach, m.in.
chemii, fizyce, ekonomii. Analiza modeli
farmakokinetycznych wymaga stosowania r.r.
Wielu z nich nie można dokładnie rozwiązać.
Tak jest np. w przypadku podania
pozanaczyniowego leków eliminowanych
zgodnie z kinetyką Michaelisa-Menten.

t

k

M

a

D

C

K

C

V

dt

dC

V











e

max

C

K

C

V

dt

dC

V

M







max

t

k

a

D

dt

dC

V



 e

Równania różniczkowe

metody rozwiązywania



metoda Eulera



metody Rungego-Kutty



metoda Bulirscha Stoera



metoda Bulirscha-Stoera

Równania różniczkowe (c.d.)

Do opisu wielu procesów używa się równań

różniczkowych cząstkowych:



przepływ krwi przez serce - r. Naviera-
Stokesa



badanie struktury związków chemicznych -
r.Schrödingera



proces uwalniania leku z tabletki - r.dyfuzji

Dla rozwiązywania r.r. cząstkowych oczywiście

również istnieją odpowiednie metody
numeryczne (met. relaksacyjne)

Równania różniczkowe

a symulacja



Rozwiązywanie równań różniczkowych
ściśle wiąże się z tzw. symulacją
procesów ciągłych, tj. modelowaniem

p

ąg y , j

układu fizycznego, biologicznego itp.
przy pomocy komputera.



Komputery, wraz z równaniami
różniczkowymi, zastępują wiele
kosztownych eksperymentów.

Całkowanie

Wielu całek pozornie prostych funkcji nie

można obliczyć analitycznie.

Oto przykłady:

Oto przykłady:

dx

x

x

dx

e

x













sin

,

1

0

2

4

Metody obliczania

całek oznaczonych



metoda prostokątów



metoda trapezów



metody Simpsona, Milne'a itp.

y

p

,

p



metody Gaussa (np. Gaussa-Legendre'a)



metoda Romberga

Metody całkowania

Całkowanie (cd.)



Metody prostokątów i trapezów są bardzo
niedokładne; tym niemniej przy wyznaczaniu
dostępności biologicznej leku (AUC) większość
b d

t

j

t d t

ó

badaczy stosuje metodę trapezów.



Dokładniejsze metody uzyskujemy przybliżając
przebieg funkcji za pośrednictwem funkcji
kwadratowej (met. Simpsona) lub wielomianu
wyższych stopni (met. Milne'a).

Całkowanie

metoda Gaussa-Legendre’a



We wszystkich powyższych metodach węzły
(punkty w których oblicza się wartość całkowanej
funkcji) są zazwyczaj w równych odległościach.



Dopuszczając nierównomierne rozmieszczenie
węzłów można otrzymać metody dokładniejsze.
Metoda Gaussa-Legendre'a pozwala dla n
węzłów scałkować bezbłędnie wszystkie
wielomiany aż do stopnia 2n-1. Lepszej metody
nie da się już wynaleźć!

Całkowanie

Porównanie metod

naprawdę trapezy Simpson Gauss



Liczba węzłów: n=5







0

sinxdx

2

1,89

1,99

2,000001

Optymalizacja



Optymalizacją nazywa się zadanie poszukiwania
minimum funkcji wielu zmiennych.



Oczywiście nie potrzeba opracowywać oddzielnych
metod maksymalizacji, bo zamiast

max { f(x) }

t

l źć

i { f( ) }

wystarczy znaleźć

min { -f(x) }

.

5

-f(x)

Najbardziej znane

metody poszukiwania minimum:



metoda Monte-Carlo



metoda pełzającego sympleksu (ameby,
Nelder-Mead)



metoda DFP (Davidon-Fletcher-Powell)



metoda Marquardta-Levenberga (dla
problemów MNK)

Metoda Monte Carlo

Metoda pełzającego sympleksu

Metoda pełzającego sympleksu

6

Najbardziej znane

metody poszukiwania minimum:



metoda Monte-Carlo



metoda pełzającego sympleksu (ameby,
Nelder-Mead)



metoda DFP (Davidon-Fletcher-Powell)



metoda Marquardta-Levenberga (dla
problemów MNK)

Optymalizacja (cd.)



Metody DFP, jak i Marquardta-Levenberga
wymagają znajomości pochodnych funkcji,
ale bywają bardzo szybkie. Dla ich powo-
d

i

i

ć

d

i

dzenia musimy znać rozsądne oszacowanie
rozwiązania.



W trudnych przypadkach zaczynamy zwykle
od metody Monte-Carlo, a potem stosujemy
amebę i/lub DFP.

Interpolacja



Mamy daną tablicę wartości funkcji w
niektórych punktach, a chcemy wyznaczyć je
w punktach pośrednich. Np. wykonujemy
pomiary stężenia leku w pewnych czasach, a

h

ć

k

chcemy narysować wykres.

t [h]

1

2

3

5

6

8

10 12 14

C [mg/l] 2,2 3,9 6,1 4,2 3,0 2,9 2,0 1,8 1,7

Interpolacja liniowa

Nie można wyświetlić obrazu. Na komputerze może brakować pamięci do otwarcia obrazu lub obraz może być uszkodzony. Uruchom ponownie komputer, a następnie otwórz plik ponownie. Jeśli czerwony znak x nadal będzie wyświetlany, konieczne może być usunięcie obrazu, a następnie ponowne wstawienie go.

Metody interpolacji



interpolacja liniowa



metoda Lagrange'a (interpolacja wielomianowa)



interpolacja funkcjami sklejanymi (ang spline)



interpolacja funkcjami sklejanymi (ang. spline)

7

Interpolacja Lagrange’a

wielomian 9. stopnia

Interpolacja Lagrange’a

wielomian 9. stopnia

Zjawisko

R

Rungego

Interpolacja funkcjami sklejanymi

(ang. spline)

Nie można wyświetlić obrazu. Na komputerze może brakować pamięci do otwarcia obrazu lub obraz może być uszkodzony. Uruchom ponownie komputer, a następnie otwórz plik ponownie. Jeśli czerwony znak x nadal będzie wyświetlany, konieczne może być usunięcie obrazu, a następnie ponowne wstawienie go.

Aproksymacja



Zadaniem aproksymacji jest przybliżone
obliczanie wartości różnych funkcji.
Najczęściej stosuje się a. wielomianami
C b

d ż

i

j

i j

Czebyszewa, gdyż zapewnia najmniejszy
błąd przy danym czasie obliczeń.



Kalkulatory i komputery obliczając funkcje
takie jak sin, ln, czy e

x

stosują aproksymację,

choć użytkownik zwykle nie zdaje sobie z
tego sprawy.