Question

Wyjaśnij i podaj przykłady i zastosowanie:

-algorytmu bisekcji

-algorytmu regułt falsi

-schematu Hornera

Answer 1

algorytm bisekcji

Metoda równego podziału (metoda połowienia, metoda bisekcji, metoda połowienia przedziału) - jedna z metod rozwiązywania równań nieliniowych. Opiera się ona na twierdzeniu Bolzano-Cauchy'ego:

Jeżeli funkcja ciągła f(x) ma na końcach przedziału domkniętego wartości różnych znaków, to wewnątrz tego przedziału, istnieje co najmniej jeden pierwiastek równania f(x) = 0.

Aby można było zastosować metodę równego podziału, muszą być spełnione założenia:

funkcja f(x) jest ciągła w przedziale domkniętym [a;b] funkcja przyjmuje różne znaki na końcach przedziału: f(a)f(b) < 0

Przebieg algorytmu:

Sprawdzić, czy pierwiastkiem równania jest punkt , czyli czy f(x1) = 0. Jeżeli tak jest, algorytm kończy się, a punkt jest miejscem zerowym. W przeciwnym razie x1 dzieli przedział [a,b] na dwa mniejsze przedziały [a,x1] i [x1,b]. Wybierany jest ten przedział, dla którego spełnione jest drugie założenie, tzn. albo f(x1)f(a) < 0 albo f(x1)f(b) < 0. Cały proces powtarzany jest dla wybranego przedziału.

Działanie algorytmu kończy się w punkcie 2 albo po osiągnięciu żądanej dokładności przybliżenia pierwiastka.

Przykład[edytuj]

Wyznaczyć pierwiastek równania x3 − x + 1 = 0 w przedziale [ − 2;2].

Rozwiązanie:

Obliczamy wartości funkcji na końcach przedziału: f( − 2) = − 5, a f(2) = 7. Dzielimy przedział na połowy: i obliczamy wartość f(x1) = 1. Ponieważ wartość funkcji dla x1 jest różna od zera, algorytm jest kontynuowany. Mamy teraz dwa przedziały [ − 2,0] i [0,2]. Wybieramy ten, na którego końcach znaki funkcji są różne - lub . Zatem pierwiastek leży w przedziale [ − 2,0] Dzielimy przedział na połowy: i obliczamy wartość funkcji f( − 1) = 1 – liczba x2 nie jest zatem pierwiastkiem. Znowu dzielimy przedział na dwa podprzedziały, wybieramy jeden z nich itd.

Uwaga: rozwiązanie można wyznaczyć z dowolną dokładnością (czyli dla każdego można znaleźć takie x0, że gdzie x jest pierwiastkiem równania), w rzadkich przypadkach można uzyskać dokładną wartość pierwiastka (gdy algorytm zostanie zakończony w punkcie 2). Algorytm metody równego podziału jest blisko spokrewniony z wyszukiwaniem binarnym.

 

 

-algorytm regułt falsi

 

Regula falsi (łac. fałszywa linia prosta, fałszywa reguła) — algorytm rozwiązywania równań nieliniowych jednej zmiennej.

Na funkcję y = f(x) nakładane są następujące ograniczenia:

W przedziale [a,b] znajduje się dokładnie jeden pojedynczy pierwiastek. Na końcach przedziału funkcja ma różne znaki: f(a)f(b) < 0. Pierwsza i druga pochodna istnieją i mają na tym przedziale stałe znaki.

Algorytm przebiega następująco:

Na początku przez punkty A = (a,f(a)) i B = (b,f(b)) przeprowadzana jest cięciwa. Punkt przecięcia x1 z osią OX jest brany jako pierwsze przybliżenie pierwiastka. Jeśli to przybliżenie jest wystarczająco dobre, algorytm kończy się. Jeśli nie, to prowadzona jest cięciwa przez punkty (x1,f(x1)) oraz A lub B – wybierany jest ten punkt, którego rzędna ma znak przeciwny do f(x1). Jednak w praktyce, dzięki ograniczeniu nr 3 już na początku algorytmu wiadomo, który z tych punktów będzie stały, tzn. wybierany za każdym razem. Następnie wyznaczane jest przecięcie nowo wyznaczonej cięciwy z osią OX (xi) i algorytm powtarza się.

Nazwa metody pochodzi od łacińskich słów: regula1 znaczące zarówno linię prostą, jak i regułę i falsus, fałszywy — metoda bazuje na fałszywym twierdzeniu (regule), że na pewnym przedziale funkcja jest liniowa. Można więc tę nazwę przetłumaczyć zarówno jako "fałszywa linia prosta" jak i "fałszywa reguła" i obydwa te tłumaczenia mają w tym kontekście sens.

Wzory[edytuj]

dla i = 1,2,...

-Schemat Hornera

Schemat Hornera – sposób obliczania wartości wielomianu dla danej wartości argumentu wykorzystujący minimalną liczbę mnożeń, jest to również algorytm dzielenia wielomianu przez dwumian . Schemat ten wiązany jest z nazwiskiem Hornera, był jednak już znany Newtonowi, Ruffiniemu i matematykom chińskim w XII wieku.

Przy dzieleniu wielomianów schemat Hornera można stosować tylko wtedy gdy w dwumianie nie ma przy żadnej potęgi i współczynnika. Dla przykładu: dla dzielenia przez dwumian można stosować schemat Hornera. Jednak dla dzielenia przez dwumian schematu Hornera stosować już nie wolno. Dla dzielenia wielomianu przez dwumian można stosować schemat Hornera, jeżeli najpierw podzieli się dwumian i wielomian, przez 3.

Jeśli dany jest wielomian , to obliczając jego wartość dla zadanego bezpośrednio z podanego wzoru należy wykonać mnożeń oraz dodawań. Tymczasem proste przekształcenie sprawia, że wystarczy jedynie mnożeń i dodawań. Mnożenia są operacją czasochłonną i eliminacja zbędnych mnożeń jest jednym z podstawowych problemów optymalizacji algorytmów.

Dla przykładu, niech:

; chcemy obliczyć wartość tego wielomianu dla

Zapisujemy:

podstawiamy

Warto dla porównania obliczyć tę wartość metodą "tradycyjną" nie korzystając z kalkulatora.

Dany wielomian

przekształcamy do postaci

Następnie definiujemy:

Tak otrzymane będzie równe Rzeczywiście, jeśli podstawimy kolejno do tego wielomianu, otrzymamy

Answer 2

algorytm bisekcji

Metoda równego podziału (metoda połowienia, metoda bisekcji, metoda połowienia przedziału) - jedna z metod rozwiązywania równań nieliniowych. Opiera się ona na twierdzeniu Bolzano-Cauchy'ego:

Jeżeli funkcja ciągła f(x) ma na końcach przedziału domkniętego wartości różnych znaków, to wewnątrz tego przedziału, istnieje co najmniej jeden pierwiastek równania f(x) = 0.

Aby można było zastosować metodę równego podziału, muszą być spełnione założenia:

funkcja f(x) jest ciągła w przedziale domkniętym [a;b] funkcja przyjmuje różne znaki na końcach przedziału: f(a)f(b) < 0

Przebieg algorytmu:

Sprawdzić, czy pierwiastkiem równania jest punkt , czyli czy f(x1) = 0. Jeżeli tak jest, algorytm kończy się, a punkt jest miejscem zerowym. W przeciwnym razie x1 dzieli przedział [a,b] na dwa mniejsze przedziały [a,x1] i [x1,b]. Wybierany jest ten przedział, dla którego spełnione jest drugie założenie, tzn. albo f(x1)f(a) < 0 albo f(x1)f(b) < 0. Cały proces powtarzany jest dla wybranego przedziału.

Działanie algorytmu kończy się w punkcie 2 albo po osiągnięciu żądanej dokładności przybliżenia pierwiastka.

Przykład[edytuj]

Wyznaczyć pierwiastek równania x3 − x + 1 = 0 w przedziale [ − 2;2].

Rozwiązanie:

Obliczamy wartości funkcji na końcach przedziału: f( − 2) = − 5, a f(2) = 7. Dzielimy przedział na połowy: i obliczamy wartość f(x1) = 1. Ponieważ wartość funkcji dla x1 jest różna od zera, algorytm jest kontynuowany. Mamy teraz dwa przedziały [ − 2,0] i [0,2]. Wybieramy ten, na którego końcach znaki funkcji są różne - lub . Zatem pierwiastek leży w przedziale [ − 2,0] Dzielimy przedział na połowy: i obliczamy wartość funkcji f( − 1) = 1 – liczba x2 nie jest zatem pierwiastkiem. Znowu dzielimy przedział na dwa podprzedziały, wybieramy jeden z nich itd.

Uwaga: rozwiązanie można wyznaczyć z dowolną dokładnością (czyli dla każdego można znaleźć takie x0, że gdzie x jest pierwiastkiem równania), w rzadkich przypadkach można uzyskać dokładną wartość pierwiastka (gdy algorytm zostanie zakończony w punkcie 2). Algorytm metody równego podziału jest blisko spokrewniony z wyszukiwaniem binarnym.

 

 

-algorytm regułt falsi

 

Regula falsi (łac. fałszywa linia prosta, fałszywa reguła) — algorytm rozwiązywania równań nieliniowych jednej zmiennej.

Na funkcję y = f(x) nakładane są następujące ograniczenia:

W przedziale [a,b] znajduje się dokładnie jeden pojedynczy pierwiastek. Na końcach przedziału funkcja ma różne znaki: f(a)f(b) < 0. Pierwsza i druga pochodna istnieją i mają na tym przedziale stałe znaki.

Algorytm przebiega następująco:

Na początku przez punkty A = (a,f(a)) i B = (b,f(b)) przeprowadzana jest cięciwa. Punkt przecięcia x1 z osią OX jest brany jako pierwsze przybliżenie pierwiastka. Jeśli to przybliżenie jest wystarczająco dobre, algorytm kończy się. Jeśli nie, to prowadzona jest cięciwa przez punkty (x1,f(x1)) oraz A lub B – wybierany jest ten punkt, którego rzędna ma znak przeciwny do f(x1). Jednak w praktyce, dzięki ograniczeniu nr 3 już na początku algorytmu wiadomo, który z tych punktów będzie stały, tzn. wybierany za każdym razem. Następnie wyznaczane jest przecięcie nowo wyznaczonej cięciwy z osią OX (xi) i algorytm powtarza się.

Nazwa metody pochodzi od łacińskich słów: regula1 znaczące zarówno linię prostą, jak i regułę i falsus, fałszywy — metoda bazuje na fałszywym twierdzeniu (regule), że na pewnym przedziale funkcja jest liniowa. Można więc tę nazwę przetłumaczyć zarówno jako "fałszywa linia prosta" jak i "fałszywa reguła" i obydwa te tłumaczenia mają w tym kontekście sens.

Wzory[edytuj]

dla i = 1,2,...

 

 

-Schemat Hornera

 

 

 

Schemat Hornera – sposób obliczania wartości wielomianu dla danej wartości argumentu wykorzystujący minimalną liczbę mnożeń, jest to również algorytm dzielenia wielomianu przez dwumian . Schemat ten wiązany jest z nazwiskiem Hornera, był jednak już znany Newtonowi, Ruffiniemu i matematykom chińskim w XII wieku.

Przy dzieleniu wielomianów schemat Hornera można stosować tylko wtedy gdy w dwumianie nie ma przy żadnej potęgi i współczynnika. Dla przykładu: dla dzielenia przez dwumian można stosować schemat Hornera. Jednak dla dzielenia przez dwumian schematu Hornera stosować już nie wolno. Dla dzielenia wielomianu przez dwumian można stosować schemat Hornera, jeżeli najpierw podzieli się dwumian i wielomian, przez 3.

Jeśli dany jest wielomian , to obliczając jego wartość dla zadanego bezpośrednio z podanego wzoru należy wykonać mnożeń oraz dodawań. Tymczasem proste przekształcenie sprawia, że wystarczy jedynie mnożeń i dodawań. Mnożenia są operacją czasochłonną i eliminacja zbędnych mnożeń jest jednym z podstawowych problemów optymalizacji algorytmów.

Dla przykładu, niech:

; chcemy obliczyć wartość tego wielomianu dla

Zapisujemy:

podstawiamy

Warto dla porównania obliczyć tę wartość metodą "tradycyjną" nie korzystając z kalkulatora.

Dany wielomian

przekształcamy do postaci

Następnie definiujemy:

Tak otrzymane będzie równe Rzeczywiście, jeśli podstawimy kolejno do tego wielomianu, otrzymamy