Mpetencji do podejmowania samodzielnych decyzji dzielimy organy na
Yüklə 496,37 Kb.
|
|
18.1.2.2. Postać normalna liniowego zagadnienia optymalizacji . . . . . . 927
18.1.3. Metoda sympleksów . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 929
18.1.3.1. Tablica sympleksów . . . . . . . . . . . . . . . . . . . . . . . . . . . 929
18.1.3.2. Przejście do nowej tablicy sympleksów . . . . . . . . . . . . . . . 929
18.1.3.3. Wyznaczenie pierwszej tablicy sympleksów . . . . . . . . . . . . 931
18.1.3.4. Zmody?kowana metoda sympleksów . . . . . . . . . . . . . . . . 932
18.1.3.5. Dualność w optymalizacji liniowej . . . . . . . . . . . . . . . . . . 934
18.1.4. Pewne szczególne liniowe problemy optymalizacji . . . . . . . . . . . . . . 935
18.1.4.1. Zagadnienie transportu . . . . . . . . . . . . . . . . . . . . . . . . 935
18.1.4.2. Zagadnienie przyporządkowania . . . . . . . . . . . . . . . . . . . 938
18.1.4.3. Zagadnienie rozkładu . . . . . . . . . . . . . . . . . . . . . . . . . . 938
18.1.4.4. Problem komiwojażera . . . . . . . . . . . . . . . . . . . . . . . . . 939
18.1.4.5. Problemy kolejkowe . . . . . . . . . . . . . . . . . . . . . . . . . . . 939
18.2. Optymalizacja nieliniowa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 939
18.2.1. Sformułowanie problemu i podstawy teoretyczne . . . . . . . . . . . . . . 939
18.2.1.1. Sformułowanie problemu . . . . . . . . . . . . . . . . . . . . . . . . 939
18.2.1.2. Warunki optymalności . . . . . . . . . . . . . . . . . . . . . . . . . 940
18.2.1.3. Dualność w optymalizacji . . . . . . . . . . . . . . . . . . . . . . . 941
18.2.2. Pewne szczególne nieliniowe zagadnienia optymalizacji . . . . . . . . . . . 941
18.2.2.1. Optymalizacja wypukła . . . . . . . . . . . . . . . . . . . . . . . . 941
18.2.2.2. Optymalizacja kwadratowa . . . . . . . . . . . . . . . . . . . . . . 942
18.2.3. Metody rozwiązywania kwadratowych zagadnień optymalizacji . . . . . . 943
18.2.3.1. Metoda Wolfego . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 943
18.2.3.2. Metoda Hildretha–d’Esopo . . . . . . . . . . . . . . . . . . . . . . 945
18.2.4. Metody numeryczne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 946
18.2.4.1. Przypadek jednowymiarowy . . . . . . . . . . . . . . . . . . . . . . 946
18.2.4.2. Poszukiwanie minimum w n-wymiarowej przestrzeni euklidesowej 947
18.2.5. Metody dla zagadnień bez więzów . . . . . . . . . . . . . . . . . . . . . . . 947
18.2.5.1. Metoda największego spadku (metoda gradientu) . . . . . . . . 947
18.2.5.2. Zastosowanie metody Newtona . . . . . . . . . . . . . . . . . . . . 948
18.2.5.3. Metoda gradientów sprzężonych . . . . . . . . . . . . . . . . . . . 948
18.2.5.4. Metoda Davidona, Fletchera i Powella (DFP) . . . . . . . . . . . 949
18.2.6. Metoda gradientu w problemach z więzami w postaci nierówności . . . . 949
18.2.6.1. Metoda kierunków dopuszczalnych . . . . . . . . . . . . . . . . . . 950
18.2.6.2. Metoda gradientów rzutowanych . . . . . . . . . . . . . . . . . . . 952
18.2.7. Metoda kar i metoda barier . . . . . . . . . . . . . . . . . . . . . . . . . . . 954
18.2.7.1. Metoda kar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 954
18.2.7.2. Metoda barier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 955
18.2.8. Metoda cięć . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 956
18.3. Dyskretna optymalizacja dynamiczna . . . . . . . . . . . . . . . . . . . . . . 957
18.3.1. Dyskretna optymalizacja dynamiczna . . . . . . . . . . . . . . . . . . . . . 957
18.3.1.1. n-poziomowe procesy decyzyjne . . . . . . . . . . . . . . . . . . . 957
18.3.1.2. Dynamiczne zagadnienia optymalizacji . . . . . . . . . . . . . . . 957
18.3.2. Przykłady dyskretnych modeli decyzyjnych . . . . . . . . . . . . . . . . . . 958
18.3.2.1. Zagadnienie zakupu . . . . . . . . . . . . . . . . . . . . . . . . . . . 958
18.3.2.2. Zagadnienie plecaka . . . . . . . . . . . . . . . . . . . . . . . . . . 958
18.3.3. Równanie funkcjonalne Bellmanna . . . . . . . . . . . . . . . . . . . . . . . 958
18.3.3.1. Własności funkcji kosztów . . . . . . . . . . . . . . . . . . . . . . . 958
18.3.3.2. Wyprowadzenie równań funkcjonalnych Bellmanna . . . . . . . . 958
18.3.4. Zasada optymalności Bellmanna . . . . . . . . . . . . . . . . . . . . . . . . 960
18.3.5. Metoda równań funkcjonalnych Bellmanna . . . . . . . . . . . . . . . . . . 960
18.3.5.1. Wyznaczenie minimalnych kosztów . . . . . . . . . . . . . . . . . 960
18.3.5.2. Wyznaczanie strategii optymalnej . . . . . . . . . . . . . . . . . . 960
18.3.6. Przykłady zastosowań metody równań funkcjonalnych . . . . . . . . . . . 961
18.3.6.1. Optymalna strategia zakupu . . . . . . . . . . . . . . . . . . . . . 961
18.3.6.2. Zagadnienie plecaka . . . . . . . . . . . . . . . . . . . . . . . . . . 962
964 19.1. Numeryczne rozwiązywanie równań nieliniowych z jedną niewiadomą 964 19.1.1. Procedura iteracji . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 964 19.1.1.1. Zwyczajna metoda iteracji . . . . . . . . . . . . . . . . . . . . . . 965 19.1.1.2. Metoda Newtona . . . . . . . . . . . . . . . . . . . . . . . . . . . . 965 19.1.1.3. Metoda interpolacji liniowej . . . . . . . . . . . . . . . . . . . . . . 966 19.1.2. Rozwiązywanie równań wielomianowych . . . . . . . . . . . . . . . . . . . . 967 19.1.2.1. Schemat Hornera . . . . . . . . . . . . . . . . . . . . . . . . . . . . 967 19.1.2.2. Położenie miejsc zerowych . . . . . . . . . . . . . . . . . . . . . . . 969 19.1.2.3. Metody numeryczne . . . . . . . . . . . . . . . . . . . . . . . . . . 970 19.2. Numeryczne rozwiązywanie układów równań . . . . . . . . . . . . . . . . . 970 19.2.1. Układy równań liniowych . . . . . . . . . . . . . . . . . . . . . . . . . . . . 971 19.2.1.1. Rozkład trójkątny macierzy . . . . . . . . . . . . . . . . . . . . . . 971 19.2.1.2. Metoda Cholesky’ego dla symetrycznej macierzy współczynników 974 19.2.1.3. Metoda ortogonalizacji . . . . . . . . . . . . . . . . . . . . . . . . . 974 19.2.1.4. Metoda Jacobiego i metoda Gaussa–Seidela . . . . . . . . . . . . 976 19.2.2. Układy równań nieliniowych . . . . . . . . . . . . . . . . . . . . . . . . . . . 978 19.2.2.1. Zwyczajna metoda iteracyjna . . . . . . . . . . . . . . . . . . . . . 978 19.2.2.2. Metoda Newtona . . . . . . . . . . . . . . . . . . . . . . . . . . . . 978 19.2.2.3. Bezróżniczkowa metoda Gaussa–Newtona . . . . . . . . . . . . . 979 19.3. Całkowanie numeryczne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 980 19.3.1. Ogólne wzory kwadraturowe . . . . . . . . . . . . . . . . . . . . . . . . . . . 980 19.3.2. Kwadratury interpolacyjne . . . . . . . . . . . . . . . . . . . . . . . . . . . . 980 19.3.2.1. Wzór prostokątów . . . . . . . . . . . . . . . . . . . . . . . . . . . 981 19.3.2.2. Wzór trapezów . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 981 19.3.2.3. Wzór trapezów Hermite’a . . . . . . . . . . . . . . . . . . . . . . . 981 19.3.2.4. Wzór Simpsona . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 982 19.3.3. Wzory kwadraturowe typu Gaussa . . . . . . . . . . . . . . . . . . . . . . 982 19.3.3.1. Wzory kwadraturowe Gaussa . . . . . . . . . . . . . . . . . . . . 982 19.3.3.2. Wzory kwadraturowe Lobatto . . . . . . . . . . . . . . . . . . . . 983 19.3.4. Metoda Romberga . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 983 19.3.4.1. Algorytm metody Romberga . . . . . . . . . . . . . . . . . . . . . 983 19.3.4.2. Zasada ekstrapolacji . . . . . . . . . . . . . . . . . . . . . . . . . . 984 19.4. Przybliżone całkowanie równań róźniczkowych zwycza jnych . . . . . . . 986 19.4.1. Zagadnienia początkowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 986 19.4.1.1. Metoda łamanej Eulera . . . . . . . . . . . . . . . . . . . . . . . . 986 19.4.1.2. Metoda Rungego–Kutty . . . . . . . . . . . . . . . . . . . . . . . . 987 19.4.1.3. Metody wielokrokowe . . . . . . . . . . . . . . . . . . . . . . . . . 987 19.4.1.4. Metoda prognostyka i korektora . . . . . . . . . . . . . . . . . . . 988 19.4.1.5. Zbieżność, konsystencja, stabilność . . . . . . . . . . . . . . . . . 989 19.4.2. Zagadnienia brzegowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 990 19.4.2.1. Metoda różnicowa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 990 19.4.2.2. Metoda postulowania postaci rozwiązania . . . . . . . . . . . . . 991 19.4.2.3. Metoda strzałów . . . . . . . . . . . . . . . . . . . . . . . . . . . . 993 19.5. Przybliżone całkowanie równań różniczkowych cząstkowych . . . . . . . 993 19.5.1. Metoda różnicowa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 993 19.5.2. Metoda postulowania rozwiązań . . . . . . . . . . . . . . . . . . . . . . . . 995 19.5.3. Metoda elementów skończonych (FEM) . . . . . . . . . . . . . . . . . . . . 996 19.6. Aproksymacja, dopasowanie, analiza harmoniczna . . . . . . . . . . . . . . 1000 19.6.1. Interpolacja wielomianami . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1000 19.6.1.1. Wzór interpolacyjny Newtona . . . . . . . . . . . . . . . . . . . . 1001 19.6.1.2. Wzór interpolacyjny Lagrange’a . . . . . . . . . . . . . . . . . . . 1001 19.6.1.3. Interpolacja według Aitkena–Neville’a . . . . . . . . . . . . . . . 1002 19.6.2. Aproksymacja w normie kwadratowej . . . . . . . . . . . . . . . . . . . . . 1003 19.6.2.1. Zagadnienie ciągłe, równania normalne . . . . . . . . . . . . . . . 1003 19.6.2.2. Zagadnienie dyskretne, równania normalne, metoda Householdera 1004 19.6.2.3. Zagadnienia wielowymiarowe . . . . . . . . . . . . . . . . . . . . . 1005 19.6.2.4. Nieliniowe zagadnienia średniej kwadratowej . . . . . . . . . . . . 1006 19.6.3. Aproksymacja Czebyszewa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1007 19.6.3.1. Sformułowanie zagadnienia i twierdzenie o alternantach . . . . . 1007 19.6.3.2. Własności wielomianów Czebyszewa . . . . . . . . . . . . . . . . . 1008 19.6.3.3. Algorytm Remesa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1009 19.6.3.4. Dyskretna aproksymacja Czebyszewa i optymalizacja . . . . . . 1010 19.6.4. Analiza harmoniczna . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1011 19.6.4.1. Wzory na interpolację trygonometryczną . . . . . . . . . . . . . 1011 19.6.4.2. Szybka transformacja Fouriera (FFT) . . . . . . . . . . . . . . . . 1012 19.7. Przedstawienie krzywych i powierzchni za pomocą funkcji sklejających 1016 19.7.1. Sześcienne funkcje sklejające . . . . . . . . . . . . . . . . . . . . . . . . . . . 1016 19.7.1.1. Interpolacyjne funkcje sklejające . . . . . . . . . . . . . . . . . . . 1016 19.7.1.2. Dopasowujące funkcje sklejające . . . . . . . . . . . . . . . . . . . 1017 19.7.2. Bisześcienne funkcje sklejające . . . . . . . . . . . . . . . . . . . . . . . . . 1018 19.7.2.1. Własności bisześciennych funkcji sklejających . . . . . . . . . . . 1018 19.7.2.2. Bisześcienne interpolacyjne funkcje sklejające . . . . . . . . . . . 1018 19.7.2.3. Bisześcienne dopasowujące funkcje sklejające . . . . . . . . . . . 1020 19.7.3. Przedstawienie Bernsteina–B´eziera dla krzywych i powierzchni . . . . . . 1020 19.7.3.1. Zasada przedstawienia B–B dla krzywych . . . . . . . . . . . . . 1021 19.7.3.2. Przedstawienie B–B dla powierzchni . . . . . . . . . . . . . . . . 1021 19.8. Wykorzystanie komputerów . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1022 19.8.1. Wewnątrzmaszynowe przedstawienia znaków . . . . . . . . . . . . . . . . . 1022 19.8.1.1. Systemy liczbowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1022 19.8.1.2. Wewnątrzmaszynowe przedstawienie liczb . . . . . . . . . . . . . 1024 19.8.2. Problemy numeryczne przy obliczeniach na komputerze . . . . . . . . . . 1025 19.8.2.1. Wprowadzenie, rodzaje błędów . . . . . . . . . . . . . . . . . . . . 1025 19.8.2.2. Znormalizowane liczby dziesiętne i zaokrąglanie . . . . . . . . . 1026 19.8.2.3. Kwestia dokładności w rachunkach numerycznych . . . . . . . . 1027 19.8.3. Biblioteki metod numerycznych . . . . . . . . . . . . . . . . . . . . . . . . . 1031 19.8.3.1. Biblioteka NAG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1032 19.8.3.2. Biblioteka IMSL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1032 19.8.3.3. Biblioteka akwizgrańska . . . . . . . . . . . . . . . . . . . . . . . . 1033 19.8.4. Zastosowanie specjalistycznych programów obliczeniowych . . . . . . . . 1033 19.8.4.1. Mathematica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1033 19.8.4.2. Maple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1037 20. PAKIETY OPROGRAMOWANIA MATEMATYCZNEGO . . . . . . . . . . 1041 20.1. Wprowadzenie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1041 20.1.1.
Krótka charakterystyka pakietów oprogramowania matematycznego . . 1041
20.1.2. Przykłady wprowadzające do głównych obszarów zastosowań . . . . . . 1042
1042
1043
1043
1043 20.1.3.
Struktura programów i obchodzenie się z pakietami obliczeniowymi . . 1044
1044 20.2. Mathematica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1045 20.2.1. Podstawowe elementy strukturalne . . . . . . . . . . . . . . . . . . . . . . 1045 20.2.2.
Rodzaje liczb w programie Mathematica . . . . . . . . . . . . . . . . . . 1046
1046
1047
1047 20.2.3.
Ważne operatory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1048
20.2.4. Listy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1049
1049
1050
1050
1050 20.2.5.
Wektory i macierze jako listy . . . . . . . . . . . . . . . . . . . . . . . . . 1051
1051
1051
20.2.6. Funkcje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1053
1053
1053
1053
20.2.7. Wzorce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1054 20.2.8.
Operatory funkcyjne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1054
20.2.9. Programowanie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1056 20.2.10.
Uzupełnienia dotyczące składni, pomocy, komunikatów . . . . . . . . . . 1057
1057
1057
1057 20.3. Maple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1058
20.3.1. Podstawowe elementy strukturalne . . . . . . . . . . . . . . . . . . . . . . 1058
1058
1059 20.3.2.
Rodzaje liczb w programie Maple . . . . . . . . . . . . . . . . . . . . . . . 1060
1060
1061
1061 20.3.3.
Ważne operatory w programie Maple . . . . . . . . . . . . . . . . . . . . 1062
20.3.4. Wyrażenia algebraiczne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1062 20.3.5. Ciągi i listy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1063 20.3.6. Struktury tabelowe i polowe, wektory i macierze . . . . . . . . . . . . . . 1064 20.3.6.1. Tabele i pola . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1064 20.3.6.2. Pola jednowymiarowe . . . . . . . . . . . . . . . . . . . . . . . . . 1065 20.3.6.3. Pola dwuwymiarowe . . . . . . . . . . . . . . . . . . . . . . . . . . 1065 20.3.6.4. Specjalne instrukcje odnoszące się do wektorów i macierzy . . . 1066 20.3.7. Funkcje i operatory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1066 20.3.7.1. Funkcje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1066 20.3.7.2. Operatory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1067 20.3.7.3. Operatory różniczkowania . . . . . . . . . . . . . . . . . . . . . . . 1068 20.3.7.4. Operator funkcyjny map . . . . . . . . . . . . . . . . . . . . . . . . 1068 20.3.8. Programowanie w Maple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1068 20.3.9. Uzupełnienia dotyczące składni, informacji i pomocy . . . . . . . . . . . . 1069 20.3.9.1. Użycie biblioteki Maple . . . . . . . . . . . . . . . . . . . . . . . . 1069 20.3.9.2. Zmienne środowiskowe . . . . . . . . . . . . . . . . . . . . . . . . . 1070 20.3.9.3. Informacja i pomoc . . . . . . . . . . . . . . . . . . . . . . . . . . . 1070 20.4. Zastosowania programów obliczeniowych . . . . . . . . . . . . . . . . . . . . 1070 20.4.1. Manipulowanie wyrażeniami algebraicznymi . . . . . . . . . . . . . . . . . 1070 20.4.1.1. Mathematica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1070 20.4.1.2. Maple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1073 20.4.2. Rozwiązywanie równań i układów równań . . . . . . . . . . . . . . . . . . 1076 20.4.2.1. Mathematica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1076 20.4.2.2. Maple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1078 20.4.3. Elementy algebry liniowej . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1080 20.4.3.1. Mathematica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1080 20.4.3.2. Maple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1082 20.4.4. Rachunek różniczkowy i całkowy . . . . . . . . . . . . . . . . . . . . . . . . 1085 20.4.4.1. Mathematica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1085 20.4.4.2. Maple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1089 20.5. Gra?ka w programach matematycznych . . . . . . . . . . . . . . . . . . . . . 1092 20.5.1. Tworzenie gra?ki za pomocą programu Mathematica . . . . . . . . . . . . 1092 20.5.1.1. Podstawy tworzenia gra?ki . . . . . . . . . . . . . . . . . . . . . . 1092 20.5.1.2. Podstawowe elementy gra?czne . . . . . . . . . . . . . . . . . . . . 1093 20.5.1.3. Opcje gra?czne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1094 20.5.1.4. Składnia przedstawień gra?cznych . . . . . . . . . . . . . . . . . . 1094 20.5.1.5. Krzywe dwuwymiarowe . . . . . . . . . . . . . . . . . . . . . . . . 1096 20.5.1.6. Parametryczne przedstawienia krzywych . . . . . . . . . . . . . . Yüklə 496,37 Kb. Dostları ilə paylaş:
|