Metoda połowienia, metoda Herona i schemat Hornera

Część algorytmów z zakresu rozszerzonego liczy na liczbach rzeczywistych: szuka miejsca zerowego funkcji, liczy pierwiastek albo wartość wielomianu. Wyniki są przybliżone, a komputer dokłada do nich własne błędy zaokrągleń, więc w każdym z tych algorytmów ważny jest warunek zatrzymania i porównywanie z tolerancją.

Każdy przykład przejdziesz krok po kroku w kursie Algorytmy: zakres rozszerzony: w przeglądarce, bez instalowania niczego i bez konta. Podgląd zmiennych pokazuje, jak przedział się zwęża, a kolejne przybliżenia zbliżają do wyniku.

Przejdź metodę połowienia krok po kroku

Miejsce zerowe metodą połowienia

Funkcja f(x) = x² - 2 ma w przedziale [1, 2] wartości -1 i 2, więc gdzieś pomiędzy przecina oś x (to pierwiastek z 2). Środek przedziału dzieli go na dwie połowy: zostaje ta, na której końcach znaki są nadal różne.

def f(x):
    return x * x - 2


a, b = 1, 2
steps = 0
while b - a > 0.001:
    s = (a + b) / 2
    if f(a) * f(s) <= 0:
        b = s
    else:
        a = s
    steps += 1
print((a + b) / 2, steps)

1.41455078125 10

Po 10 krokach przedział ma długość 1/1024, a jego środek różni się od √2 = 1,41421… o mniej niż 0,0005. Ten sam program znajdzie miejsce zerowe każdej funkcji ciągłej, jeśli tylko na końcach przedziału ma ona różne znaki.

Pierwiastek metodą Herona i błędy obliczeń

Metoda Herona poprawia przybliżenie x pierwiastka z p wzorem x = (x + p / x) / 2. Zbiega dużo szybciej niż połowienie:

p = 2
x = p
while abs(x * x - p) > 0.000001:
    x = (x + p / x) / 2
    print(x)

1.5
1.4166666666666665
1.4142156862745097
1.4142135623746899

Cztery kroki wystarczają do dokładności 0,000001. Warunek pętli porównuje x · x z p z tolerancją: przy liczbach rzeczywistych równość prawie nigdy nie zachodzi dokładnie, bo komputer pamięta je w systemie dwójkowym z ograniczoną liczbą cyfr:

print(0.1 + 0.2)
print(0.1 + 0.2 == 0.3)
print(abs(0.1 + 0.2 - 0.3) < 1e-9)
print(1e16 + 1 - 1e16)

0.30000000000000004
False
True
0.0

Ostatni wiersz to utrata cyfr: do bardzo dużej liczby dodana jedynka znika, bo nie mieści się w dostępnej dokładności.

Schemat Hornera

Wielomian 2x³ - 6x² + 2x - 1 można zapisać jako ((2x - 6)x + 2)x - 1. Wtedy wartość liczy się od lewej: mnożenie przez x i dodanie kolejnego współczynnika. Ta sama pętla zamienia liczbę z dowolnego systemu na dziesiętny:

coefficients = [2, -6, 2, -1]
x = 3
value = coefficients[0]
for c in coefficients[1:]:
    value = value * x + c
print(value)


def to_decimal(digits, base):
    value = 0
    for c in digits:
        value = value * base + "0123456789ABCDEF".index(c)
    return value


print(to_decimal("1011", 2), to_decimal("FF", 16), to_decimal("777", 8))
print(int("FF", 16))

5
11 255 511
255

Wbudowane int(napis, podstawa) robi to samo, ale na maturze trzeba umieć napisać tę pętlę, np. dla systemów, których int nie obsługuje w treści zadania. Zamianę w drugą stronę (z dziesiętnego) opisuje strona systemy liczbowe.

Lista kroków, pseudokod i schemat blokowy

Podstawa programowa wymaga, żeby uczeń opisywał problem specyfikacją (dane i wynik) i zapisywał algorytm listą kroków albo pseudokodem, a w szkole rysuje się też schematy blokowe. Pseudokod jest w stylu arkuszy maturalnych: ← to przypisanie, div i mod to iloraz i reszta z dzielenia całkowitego, a elementy tablic i znaki napisów są numerowane od 1 (w Pythonie od 0). Te same zapisy są w kursie przy lekcjach tematu, pod przyciskiem Algorytm.

Miejsce zerowe metodą połowienia przedziału

Specyfikacja. Dane: funkcja f ciągła w przedziale [a, b], f(a) i f(b) różnych znaków (tu f(x) = x² - 2), dokładność e > 0. Wynik: przybliżenie miejsca zerowego f z błędem najwyżej e / 2.

Lista kroków:

1. Wczytaj końce przedziału a i b oraz dokładność e.
2. Jeśli b - a ≤ e, przejdź do kroku 5.
3. Oblicz środek s = (a + b) / 2. Jeśli f(a) i f(s) mają różne znaki albo f(s) = 0, zastąp b liczbą s. W przeciwnym razie zastąp a liczbą s.
4. Wróć do kroku 2.
5. Wypisz środek przedziału (a + b) / 2.

Pseudokod:

funkcja f(x)
  zwróć x * x - 2
wczytaj a, b, e
dopóki b - a > e wykonuj
  s ← (a + b) / 2
  jeżeli f(a) * f(s) ≤ 0 to
    b ← s
  w przeciwnym razie
    a ← s
wypisz (a + b) / 2

Schemat blokowy:

Pierwiastek kwadratowy metodą Herona

Specyfikacja. Dane: liczba p > 0 i dokładność e > 0. Wynik: przybliżenie x pierwiastka z p, takie że |x · x - p| ≤ e.

Lista kroków:

1. Wczytaj liczbę p i dokładność e.
2. Przyjmij pierwsze przybliżenie x = p.
3. Jeśli |x · x - p| ≤ e, przejdź do kroku 5.
4. Zastąp x średnią liczb x i p / x, czyli (x + p / x) / 2, i wróć do kroku 3.
5. Wypisz x.

Pseudokod:

wczytaj p, e
x ← p
dopóki |x * x - p| > e wykonuj
  x ← (x + p / x) / 2
wypisz x

Schemat blokowy:

Wartość wielomianu schematem Hornera

Specyfikacja. Dane: stopień n, współczynniki A[1..n + 1] od najwyższej potęgi, liczba x. Wynik: wartość wielomianu A[1] · xⁿ + A[2] · xⁿ⁻¹ + … + A[n + 1] w punkcie x.

Lista kroków:

1. Wczytaj n, współczynniki A[1..n + 1] i liczbę x.
2. Ustaw w = A[1].
3. Dla i = 2, 3, …, n + 1 zastąp w liczbą w · x + A[i].
4. Wypisz w.

Pseudokod:

wczytaj n, A, x
w ← A[1]
dla i = 2, 3, ..., n + 1 wykonuj
  w ← w * x + A[i]
wypisz w

Schemat blokowy:

Liczba z systemu o podstawie p na dziesiętny

Specyfikacja. Dane: napis s z cyframi liczby (0-9, A-F) i podstawa p (2 ≤ p ≤ 16). Wynik: wartość liczby w systemie dziesiętnym.

Lista kroków:

1. Wczytaj napis s i podstawę p. Ustaw w = 0.
2. Dla kolejnych znaków c napisu s od lewej wykonaj kroki 3-4.
3. Zamień znak c na wartość cyfry d: litery A-F to 10-15, cyfry 0-9 to ich wartości.
4. Zastąp w liczbą w · p + d (schemat Hornera).
5. Wypisz w.

Pseudokod:

wczytaj s, p
w ← 0
dla i = 1, 2, ..., długość(s) wykonuj
  c ← s[i]
  jeżeli c ≥ "A" to
    d ← kod(c) - kod("A") + 10
  w przeciwnym razie
    d ← kod(c) - kod("0")
  w ← w * p + d
wypisz w

Schemat blokowy:

Najczęstsze błędy

• Porównanie liczb rzeczywistych przez ==. Warunek x * x == p może nigdy nie być spełniony i pętla nie skończy się. Porównuj z tolerancją.
• Zły wybór połowy. W połowieniu zostaje ta połowa, na której końcach znaki są różne: iloczyn f(a) · f(s) ≤ 0. Pomylony znak nierówności przesuwa przedział poza miejsce zerowe.
• Przedział bez zmiany znaku. Jeśli f(a) i f(b) mają ten sam znak, metoda połowienia nie gwarantuje niczego. Sprawdź to przed pętlą.
• Współczynniki w złej kolejności. Schemat Hornera zaczyna od współczynnika przy najwyższej potędze. Brakujące potęgi trzeba wpisać jako 0.

Ćwicz w przeglądarce

W kursie Algorytmy: zakres rozszerzony metody numeryczne zajmują trzy tematy:

• połowienie z zadaną dokładnością,
• rozwiązanie równania cos x = x,
• pierwiastek metodą Herona,
• porównanie liczb rzeczywistych z tolerancją,
• wartość wielomianu schematem Hornera.

Przycisk Algorytm przy tych lekcjach pokazuje listę kroków, pseudokod i schemat blokowy bez wychodzenia z edytora. Pełna lista: algorytmy.

Dla nauczycieli

Metody numeryczne dobrze pokazać na tabeli przebiegu: krokowanie wypisuje kolejne przedziały i przybliżenia, a uczniowie sami sprawdzają, ile kroków potrzeba dla danej dokładności. W BitWizards przydzielasz kurs klasie i widzisz przebieg pisania kodu każdego ucznia. Platforma jest darmowa dla szkół - jak zacząć.