Зачем программисту искать корни уравнений?

В школе мы решали уравнения по формулам: квадратное — через дискриминант, линейное — переносом слагаемых. Но в реальной разработке 90% уравнений не имеют аналитического решения.

Где это встречается в IT

• Игры и физика: рассчитать, где мяч пересечёт землю (решение уравнения движения).
• Графика и 3D: найти точку пересечения луча с объектом (ray tracing — трассировка лучей).
• Финансы: вычислить внутреннюю норму доходности (IRR — Internal Rate of Return, внутренняя норма рентабельности) инвестиционного проекта.
• Машинное обучение: минимизировать функцию потерь (это тоже поиск корня производной).
• Инженерия: рассчитать нагрузку на конструкцию, частоту колебаний, теплопередачу.

План лекции

Что мы разберём за одну пару:

1. Постановка задачи: что такое корень уравнения.
2. Алгебраические и трансцендентные уравнения.
3. Почему нельзя решить всё аналитически.
4. Два этапа решения: отделение корней и уточнение.
5. Графический метод локализации.
6. Аналитический метод локализации (теорема о промежуточном значении).
7. Метод половинного деления (бисекции) — теория и алгоритм.
8. Блок-схема метода бисекции.
9. Пример на Python: метод половинного деления.
10. Метод простой итерации — теория.
11. Условия сходимости итераций.
12. Пример на Python: метод итераций.
13. Сравнение методов и скорость сходимости.
14. Анонс практической работы №2.
15. Вопросы для самопроверки и итоги.

Постановка задачи: что такое корень уравнения

Рассмотрим уравнение вида:

f(x) = 0

где f(x) — заданная функция, а x — неизвестная величина, которую нужно найти.

Корень уравнения — это такое значение x, при котором функция f(x) обращается в ноль. Геометрически — это точка пересечения графика функции с осью Ox (абсцисс — горизонтальной осью).

Пример

Уравнение x² − 4 = 0 имеет два корня: x = 2 и x = −2. На графике параболы y = x² − 4 это точки, где кривая пересекает горизонтальную ось.

Алгебраические и трансцендентные уравнения

Все уравнения делятся на два больших класса. Понимание этой разницы — ключ к выбору метода решения.

Почему нельзя решить всё аналитически?

«Аналитически» — значит по формуле, точно, без приближений. Как x = (−b ± √D) / (2a) для квадратного уравнения.

Проблемы аналитического подхода

• Уравнения 5-й степени и выше не решаются в радикалах (доказано Нильсом Абелем).
• Трансцендентные уравнения типа cos(x) = x не имеют точной формулы решения.
• Функции, заданные таблично или графиком (например, данные с датчика) — формулы просто нет.
• Сложные инженерные задачи — уравнения с тысячами слагаемых.

Пример: уравнение cos(x) = x имеет корень x ≈ 0.7390851332. Точной формулы нет, но компьютер найдёт это значение за миллисекунды.

Два этапа решения уравнения

Численное решение любого уравнения всегда состоит из двух последовательных этапов. Пропустить один из них — нельзя.

Графический метод локализации

Самый наглядный способ — построить график функции y = f(x) и посмотреть, где он пересекает ось Ox.

Как это делается

1. Выбираем диапазон значений x (например, от −5 до 5).
2. Вычисляем f(x) в нескольких точках (с шагом 0.5 или 0.1).
3. Строим график (вручную на миллиметровке или в Python через matplotlib).
4. Видим, где график пересекает горизонтальную ось — это и есть корни.

Пример на Python

import numpy as np
import matplotlib.pyplot as plt

x = np.linspace(-5, 5, 400)
y = np.cos(x) - x  # наше уравнение cos(x) = x

plt.axhline(0, color='black', linewidth=1)
plt.plot(x, y, label='f(x) = cos(x) - x')
plt.grid(True)
plt.legend()
plt.title('Графическая локализация корня')
plt.show()

На графике видно: кривая пересекает ось один раз, примерно в точке x ≈ 0.7. Значит, корень один, и он находится на отрезке [0, 1].

Аналитический метод локализации

Если графика под рукой нет, используем математику. В основе — теорема о промежуточном значении (теорема Больцано — Коши).

Алгоритм перебора

1. Задаём начальный диапазон [x₀, x₁] и шаг h.
2. Вычисляем f(x₀), f(x₁), f(x₂), … с шагом h.
3. Ищем две соседние точки, где функция меняет знак.
4. Отрезок между ними — это «отделённый корень».

Пример

Уравнение x³ − x − 1 = 0. Считаем:

• f(1) = 1 − 1 − 1 = −1 (отрицательно)
• f(2) = 8 − 2 − 1 = 5 (положительно)

Знак изменился → на отрезке [1, 2] есть корень.

Метод половинного деления (бисекции)

Теперь, когда мы знаем, что на отрезке [a, b] есть ровно один корень, нужно его уточнить. Самый простой и надёжный метод — метод половинного деления (он же метод бисекции, от лат. bisectio — рассечение надвое).

Идея метода

Делим отрезок пополам, выбираем ту половину, где функция меняет знак, и повторяем. И так до тех пор, пока отрезок не станет достаточно малым.

Алгоритм пошагово

1. Заданы [a, b] и точность ε.
2. Находим середину: c = (a + b) / 2.
3. Вычисляем f(c).
4. Если f(c) = 0 (или |f(c)| < ε) — корень найден: x = c.
5. Если f(a) · f(c) < 0 — корень в левой половине: b = c.
6. Иначе — корень в правой половине: a = c.
7. Повторяем шаги 2–6, пока |b − a| < ε.

Блок-схема метода бисекции

Визуально алгоритм выглядит так:

Сколько шагов нужно?

Метод бисекции имеет важную особенность — мы можем точно предсказать, сколько итераций (шагов) потребуется.

Формула оценки числа шагов

n ≥ log₂((b − a) / ε)

где n — число шагов, (b − a) — длина исходного отрезка, ε — требуемая точность.

Пример

Отрезок [1, 2] (длина 1), точность ε = 0.001.

n ≥ log₂(1 / 0.001) = log₂(1000) ≈ 9.97 → нужно 10 шагов

Видно: чтобы добавить ещё один верный знак после запятой, нужно примерно 3–4 дополнительных шага. Это плата за надёжность метода.

Пример на Python: метод бисекции

Решим уравнение cos(x) − x = 0 на отрезке [0, 1] с точностью ε = 10⁻⁶.

def f(x):
    """Наша функция: cos(x) - x"""
    import math
    return math.cos(x) - x

def bisection(a, b, epsilon):
    """Метод половинного деления"""
    step = 0
    while abs(b - a) > epsilon:
        c = (a + b) / 2
        step += 1
        print(f"Шаг {step}: a={a:.6f}, b={b:.6f}, c={c:.6f}, f(c)={f(c):.6f}")
        
        if f(c) == 0:
            return c
        elif f(a) * f(c) < 0:
            b = c  # корень в левой половине
        else:
            a = c  # корень в правой половине
    
    return (a + b) / 2

# Запуск
root = bisection(0, 1, 1e-6)
print(f"\nКорень найден: x ≈ {root:.8f}")
print(f"Проверка: f(x) = {f(root):.2e}")

Результат работы

Шаг 1: a=0.000000, b=1.000000, c=0.500000, f(c)=0.377583
Шаг 2: a=0.500000, b=1.000000, c=0.750000, f(c)=-0.018311
...
Шаг 20: a=0.739085, b=0.739086, c=0.739085, f(c)=0.000000

Корень найден: x ≈ 0.73908513
Проверка: f(x) = 2.22e-16

Метод простой итерации

Второй по популярности метод — метод простой итерации. Он быстрее бисекции, но требует аккуратной подготовки уравнения.

Идея метода

Преобразуем уравнение f(x) = 0 к виду:

x = φ(x)

где φ(x) — некоторая функция, полученная из f(x). Затем строим итерационный процесс:

xₙ₊₁ = φ(xₙ)

Начинаем с некоторого x₀ (приближения) и последовательно вычисляем x₁, x₂, x₃, … до сходимости.

Пример преобразования

Уравнение x³ − x − 1 = 0. Преобразуем:

x³ = x + 1 → x = ∛(x + 1)

Теперь φ(x) = ∛(x + 1). Берём x₀ = 1 и считаем:

• x₁ = ∛(1 + 1) = ∛2 ≈ 1.2599
• x₂ = ∛(1.2599 + 1) = ∛2.2599 ≈ 1.3122
• x₃ = ∛(1.3122 + 1) ≈ 1.3227
• … и так далее, пока значения не перестанут меняться.

Условия сходимости итераций

Метод итерации не всегда сходится. Если преобразовать уравнение неудачно, процесс может «разбегаться» в бесконечность.

Как проверить на практике

1. Найти производную φ'(x).
2. Подставить в неё границы отрезка [a, b].
3. Если |φ'(x)| < 1 на всём отрезке — метод сойдётся.
4. Если |φ'(x)| ≥ 1 — нужно преобразовать уравнение по-другому.

Плохой пример

Уравнение x³ − x − 1 = 0. Преобразуем неудачно: x = x³ − 1. Тогда φ'(x) = 3x². При x ≈ 1.3 получаем φ'(x) ≈ 5.07 > 1 — метод разойдётся!

Пример на Python: метод итераций

Решим то же уравнение x³ − x − 1 = 0 методом простой итерации.

def phi(x):
    """Преобразованная функция: x = ∛(x + 1)"""
    return (x + 1) ** (1/3)

def simple_iteration(x0, epsilon, max_iter=100):
    """Метод простой итерации"""
    x = x0
    for n in range(max_iter):
        x_new = phi(x)
        print(f"Итерация {n+1}: x = {x_new:.8f}")
        
        if abs(x_new - x) < epsilon:
            return x_new
        x = x_new
    
    print("Метод не сошёлся за заданное число итераций!")
    return None

# Запуск
root = simple_iteration(1.0, 1e-6)
print(f"\nКорень найден: x ≈ {root:.8f}")

Результат работы

Итерация 1: x = 1.25992105
Итерация 2: x = 1.31229384
Итерация 3: x = 1.32271116
...
Итерация 28: x = 1.32471796
Итерация 29: x = 1.32471796

Корень найден: x ≈ 1.32471796

Сравнение методов

Какой метод выбрать? Зависит от задачи. Давайте сравним два рассмотренных.

Скорость сходимости: что это такое

Скорость сходимости — это то, как быстро метод приближается к точному корню. Измеряется порядком метода p.

Виды сходимости

• Линейная (p = 1): на каждом шаге ошибка уменьшается в постоянное число раз. Так работают бисекция и простая итерация.
• Квадратичная (p = 2): число верных знаков удваивается на каждом шаге. Так работает метод Ньютона (о нём — на следующей лекции).
• Суперлинейная: быстрее линейной, но медленнее квадратичной.

Наглядный пример

Если текущая ошибка 10⁻²:

• Линейная сходимость: следующая ошибка 10⁻³ (добавили 1 знак).
• Квадратичная: следующая ошибка 10⁻⁴ (удвоили число знаков).

Встроенные функции Python

В реальных проектах не пишут свои методы с нуля — используют готовые библиотеки. В Python это scipy.optimize.

from scipy.optimize import root_scalar
import math

def f(x):
    return math.cos(x) - x

# Метод бисекции
result = root_scalar(f, bracket=[0, 1], method='bisect', xtol=1e-8)
print(f"Бисекция: x = {result.root:.10f}, итераций: {result.iterations}")

# Метод Brent (комбинация бисекции, секущих и обратной квадратичной интерполяции)
result = root_scalar(f, bracket=[0, 1], method='brentq', xtol=1e-8)
print(f"Brent: x = {result.root:.10f}, итераций: {result.iterations}")

Результат

Бисекция: x = 0.7390851332, итераций: 27
Brent: x = 0.7390851332, итераций: 6

Но чтобы грамотно использовать библиотеки, нужно понимать, как работают базовые методы. Иначе вы не сможете выбрать правильный инструмент для задачи.

Прикладной пример: физика в играх

Рассмотрим реальную задачу из игровой разработки. Игрок бросает мяч с начальной скоростью v₀ = 20 м/с под углом α = 45°. Нужно найти, когда мяч упадёт на землю.

Математическая модель

Уравнение движения по вертикали (с учётом сопротивления воздуха, пропорционального скорости):

y(t) = v₀·sin(α)·t − (g/2)·t² − k·t³ = 0

где g = 9.81 м/с² — ускорение свободного падения, k = 0.05 — коэффициент сопротивления.

Это кубическое уравнение относительно t. Аналитически решить можно, но сложно. Проще — численно.

import math

def y(t):
    v0, alpha, g, k = 20, math.radians(45), 9.81, 0.05
    return v0 * math.sin(alpha) * t - (g/2) * t**2 - k * t**3

# Локализация: проверяем значения
for t in [0, 1, 2, 3, 4]:
    print(f"t={t}: y={y(t):.3f}")

# Видно: y(2) > 0, y(3) < 0 → корень на [2, 3]
# Уточняем бисекцией:
# ... (код из слайда 13)

Результат: мяч упадёт примерно через t ≈ 2.73 секунды. Именно так работают физические движки игр.

Анонс практической работы №2

На следующей паре мы проведём Практическую работу №2 по теме «Решение алгебраических и трансцендентных уравнений методом половинного деления и методом итераций» (2 академических часа).

Что вас ждёт

• Задание 1: графически локализовать корни уравнения (построить график в Python).
• Задание 2: аналитически отделить корни (метод перебора с шагом).
• Задание 3: реализовать метод половинного деления на Python.
• Задание 4: реализовать метод простой итерации.
• Задание 5: сравнить результаты обоих методов и сделать вывод.

Вопросы для самопроверки (часть 1)

1. Что такое корень уравнения? Дайте определение.
2. Чем алгебраическое уравнение отличается от трансцендентного? Приведите примеры.
3. Почему уравнения 5-й степени и выше нельзя решить по общей формуле?
4. Что значит «решить уравнение аналитически»? А «численно»?
5. Из каких двух этапов состоит численное решение уравнения?
6. В чём суть графического метода локализации?
7. Сформулируйте теорему о промежуточном значении (теорему Больцано — Коши).
8. Как аналитически отделить корни уравнения?

Вопросы для самопроверки (часть 2)

9. В чём идея метода половинного деления (бисекции)?
10. Запишите алгоритм метода бисекции пошагово.
11. По какой формуле оценивается число шагов метода бисекции?
12. Каковы преимущества и недостатки метода бисекции?
13. В чём идея метода простой итерации?
14. Как преобразовать уравнение f(x) = 0 к виду x = φ(x)?
15. При каком условии метод итераций сходится?
16. Что такое скорость сходимости? Какие виды сходимости вы знаете?
17. Какой метод быстрее: бисекция или итерация? Почему?
18. Какие встроенные функции Python можно использовать для поиска корней?

Что должен уметь студент после этой лекции

После изучения этой темы и выполнения практической работы вы должны:

Домашнее задание

1. Повторить материал лекции: определения, алгоритмы, условия сходимости.
2. Решить вручную (на бумаге) уравнение x³ − 2x − 5 = 0 методом бисекции на отрезке [2, 3] с точностью ε = 0.1. Сделать 4 шага.
3. Творческое задание (со звёздочкой): написать на Python программу, которая сравнивает скорость работы метода бисекции и метода итераций для уравнения cos(x) − x = 0. Вывести число итераций и время работы каждого метода (используйте модуль time).
4. Прочитать в учебнике Лапчика М.П. «Элементы численных методов» главу 2 (раздел о методе половинного деления).
5. Подготовиться к практической работе №2: установить Python, проверить работу matplotlib.

import time
start = time.time()
# ... ваш код ...
end = time.time()
print(f"Время работы: {end - start:.6f} секунд")

Типичные ошибки студентов

На практических работах часто встречаются одни и те же промахи. Избегайте их!

Итоги лекции

Сегодня мы сделали огромный шаг вперёд — перешли от теории погрешностей к реальным численным алгоритмам.

Краткое резюме

• Большинство уравнений в реальных задачах не решаются аналитически.
• Численное решение состоит из двух этапов: локализация и уточнение.
• Метод бисекции — надёжный, но медленный. Всегда сходится.
• Метод итераций — быстрее, но требует аккуратной подготовки (|φ'(x)| < 1).
• В реальных проектах используют комбинации методов (например, метод Brent).
• В Python есть готовые инструменты: scipy.optimize.root_scalar.