Начало: Математика для чайников. Глава 1. Что такое математическая абстракция.
Численные методы – это один из мощных инструментов математики, который применяется, в том числе, и в IT-науках (в программировании). Надо сказать, что различные математические задачи можно решать как аналитически, так и численно. Например, нам надо решить уравнение:
Данное уравнение задано в переменных, и решить его означает решить именно аналитически:
Если нам известны значения переменных a и b, мы можем подставить в найденную формулу и вычислить конкретное значение x. Это значит, что мы решили уравнение численно.
Строго говоря, обычно в качестве решения нам нужно именно число, вычисленное с определенной точностью. Но тогда встает вопрос, а обязательно ли выводить формулу для x, чтобы решить уравнение? И, на самом деле, нет. Более того, часто найти формулу для x вообще очень затруднительно. Вот как, например, решить такое уравнение:
Если нам надо найти x, причем, точность этого x ограничена определенным количество знаков после запятой, то почему бы не попробовать решить перебором? Если мы знаем диапазон x, то мы можем пройти по диапазону с нужным шагом и вычислить каждое значение функции. Правда, если x надо вычислить очень точно, то у нас может быть огромное количество итераций и компьютер будет долго считать. Как тут быть? Очень просто, в численных методах есть множество алгоритмов постепенно приближения, которые решают задачу за гораздо меньшее количество итераций, чем полный перебор.
Рассмотрим один из таких алгоритмов: метод Ньютона, который применяется для решения уравнений, сводимых к выражению f(x)=0. Суть метода заключается в том, что мы берем какое-то начальное приближение для x, по специальной формуле считаем новое значение, затем вычисляем значение функции. Если это значение достаточно близко к нулю, значит, мы нашли x. Вот эта формула:
Функция со штрихом – f’ означает производную.
Что такое производная я писал в уроках:
· Математика для чайников. Глава 9. Основы матанализа | Александр Шуравин. | Яндекс Дзен (yandex.ru)
· Математика для чайников. Глава 14. Производная | Александр Шуравин. | Яндекс Дзен (yandex.ru)
Геометрический смысл метода Ньютона заключается в том, что строится касательная к графику функции и проводится до пересечения с осью Ox. Эта точка является точкой следующего приближения:
Но тут, как говорится, есть нюансы. Во-первых, как определить точку начального приближения. Во-вторых, у уравнения может быть несколько корней. Начну, собственно, со второго вопроса, так как первый вытекает из него. Как посчитать количество корней уравнения? Очевидно, что количество корней – это количество точек, в которых f(x)=0, то есть график функции пересекает ось Ox. Для начала вспомним, что такое промежутки монотонности. Это такие промежутки, на которых функция либо монотонно возрастает, либо монотонно убывает. Для того, чтобы определить эти самые промежутки монотонности, надо определить точки перегиба ее графика. Если нам будут известны точки перегиба, то мы найдем, сколько раз функция пересекает ось Ox.
И так, допустим, у нас есть вот такой вот примерный график функции:
Допустим, мы нашли ее предел при минус бесконечности, и он положительный. А самая левая точка перегиба лежит ниже оси Ox (значение функции отрицательно). Очевидно, что где-то между минус бесконечностью и этой точкой график пересекает ось Ox. Аналогично, ищем следующую точку перегиба, он выше оси Ox, значит, и тут график ее пересекает. И так исследуем все промежутки монотонности. На графике мы можем насчитать 5 пересечений – пять корней уравнения.
Ну, и другой вопрос: как выбрать начальное приближение. Очевидно, надо выбрать точку где-то посередине между точками перегиба. Ну кроме крайних случаев, мы не может найти середину бесконечности. Значит надо найти точки чуть левее самого левого перегиба и чуть правее самого правого. Главное, чтобы производная в этой точке не была равна нулю. Если производная равна нулю – то это точка перегиба. Более того, если вы попытаетесь в этой точке использовать формулу, то получите деление на нуль.
А теперь попробуем решить при помощи данного метода кубическое уравнение:
Для начала нам надо вычислить точки перегиба функции. Находим ее производную:
У нас получилось квадратное уравнение. Его решение известно, проходят в школе. Давайте решим:
Проверим, правильно ли мы решили данное уравнение, посчитаем хотя бы в Excel:
Теперь определим промежутки монотонности:
Определим направление изменения функции на этих промежутках, для этого нам надо выяснить ее значения на концах промежутков.
Определим на самом левом конце первого промежутка:
На правом конце:
Мы посчитали примерно и нам кажется очевидным, что:
Но в таких случаях лучше бы в этом убедиться. Как? Посчитать значения функции еще раз, но для аргумента значением чуть ниже:
Функция у нас монотонно возрастающая, мы чуть-чуть уменьши аргумент, уменьшалось и значение функции но не до нуля. Значит, теперь мы точно уверены что:
Теперь смотрите. При минус бесконечности предел функции стремится к минус бесконечности, а в точке перегиба она принимает положительное значение. Следовательно, на данном промежутке монотонности график функции пересекает нулевой уровень.
Теперь посмотрим следующий промежуток монотонности:
И так, мы видим, что в следующей точке перегиба значение функции отрицательное. Следовательно, на этой интервале функция тоже пересекает нулевой уровень. Ну и последний промежуток монотонности:
Таким образом, на этом промежутке уже в третий раз график функции пересекает нуль. Итого, уравнение имеет три корня. В этом мы, кстати, можем убедиться, если построим график:
Можно, конечно, примерно найти корни по графику. Но мы этого делать не будем, мы найдем точно при помощи метода Ньютона.
Давайте выберем начальное приближение для первого корня. Очевидно, оно должно быть где-то слева от первого перегиба:
Пусть это будет 1.2. Строим формулу в Excel:
Как видим, мы достаточно точно решили уравнение за 5 итераций. Ответ: 1.
Найдем второй корень, точку начального приближения возьмем чуть правее:
Ответ: 3
И у нас где-то еще затерялся третий корень. Если мы посмотрим на таблицу, то от x=1.45 у нас сразу решение скачет на больше 5, что явно уже на третьем промежутке. Там корня быть не может. Он где-то между 1 и 3. Так что в этом диапазоне надо поиграться с начальным приближением. Например, поставить 1.6:
Вот мы и начли третий корень: 2.
Ну и напоследок, расскажу о том, где еще можно применить численные методы, кроме решений уравнений:
· Решение задач оптимизации. Под задачей оптимизации подразумевается задача, в которой дана некая целевая функция, и нужно найти либо минимум, либо максимум. Часто в задаче оптимизации задана система ограничений. Пример такой задачи – максимизировать прибыль или минимизировать издержи (в экономике). В IT-науках классическая задача оптимизации – это обучение модели Machine Learning-а, например, нейронной сети. В этом случае требуется минимизировать ошибку.
· Задачи интерполяции и приближенного вычленяя функции. Под интерполяцией понимается нахождение неизвестных промежуточных значений некоторой функции, по имеющемуся дискретному набору её известных значений. Способы интерполяции бывают разными. Самый простой – это линейная интерполяция. Например, если при x=2 значение функции 4, а при x=4 значение функции 16, то можно предположить, что при x=3 значение функции будет 4+(16-4)/(4-2)*(4-3)=4+12/2*1=4+6=10. Но, надо понимать, что если функция нелинейная, то такой метод может быть весьма неточным. Например, если это функция «x в квадрате», то правильно значение функции будет 8. Правда, если мы знаем, какая это функция, то интерполяция нам не нужна – мы можем просто вычислить. А вот если не знаем – то тут да, только интерполяция, только хардкор.
· Численное интегрирование. Что такое интеграл можно почитать тут: Математика для чайников. Глава 9. Основы матанализа | Александр Шуравин. | Яндекс Дзен (yandex.ru)
· Решение систем уравнений. Конечно же, при помощи численных методов можно решать не просто одно уравнение, а целые системы уравнений. В том числе, нелинейные. И даже дифференциальные.
Следующая глава: Математика для чайников. Глава 18. Методы математической оптимизации
