Численные методы решения задач. В чём их преимущества?

Численные методы решения задач при наличии компьютера и навыка программирования позволяют в ряде случаев существенно упростить и ускорить решение, а также, наглядно продемонстрировать преимущества полноценного владения компьютером.

Давайте рассмотрим пример простой типовой задачи, какие довольно часто возникают в повседневной жизни различных специалистов.

Допустим, нам требуется найти точку, в которой пересекаются две функции. Такие задачи встречаются очень часто, хотя и выглядят в изначальных формулировках несколько по-другому, однако, если формализовать исходную задачу, мы придем к подобной задаче: либо поиск точки пересечения двух функций, либо поиск корней уравнения, что одно и то же. Для большей простоты мы будем искать точку пересечения двух прямых, заданных уравнениями

$\mathit{y}\mathbf{\left(}\mathit{x}\mathbf{\right)}\mathbf{=}\mathbf{2}\mathit{x}\mathbf{+}\mathbf{1}$

и

$\mathit{g}\mathbf{\left(}\mathit{x}\mathbf{\right)}\mathbf{=}\mathbf{5}\mathbf{—}\mathit{x}$

С подобными задачами школьники в первый раз сталкиваются примерно в 6-7 классе при изучении функций.

С помощью графического решения (построения графиков функций) всегда можно уточнить количество точек пересечения функций (корней системы уравнений) и их примерные значения. А аналитическое решение даст нам точные результаты. Лучше всего совмещать оба этих метода для лучшего понимания задачи и быстрого получения результата.

Для начала попробуем решить задачу графически. Например, это можно сделать с помощью программы (или онлайн-сервиса) GeoGebra.

Мы видим, что эти графики пересекаются в точке, где

$\mathit{х}\mathbf{\approx }\mathbf{1}\mathbf{.}\mathbf{33}, а \mathit{y}\mathbf{\approx }\mathbf{3}\mathbf{.}\mathbf{63}.$

Теперь решим эту задачу аналитически для того, чтобы найти точное значение x и y.

В случае, когда мы имеем простое аналитическое решение задачи, применять численные методы нет необходимости. Любую задачу нужно решать оптимально — с точки зрения времени и прочих затрат.

Давайте теперь рассмотрим немного другой пример. Найдем точку, в которой пересекаются функции:

y(x) = 2x³ + x² — x

и

g(x) = 5 — x

Построим графики, которые продемонстрируют нам, что решение уравнения

y(x) = g(x)
2x³ + x² — x = 5 — x

идентично уравнению

y(x) — g(x) = 0
2x³ + x² — x — 5 + x = 0
2x³ + x² — 5 = 0

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

Вот в этом случае для упрощения и ускорения решения (особенно, когда нужен численный результат, а не алгебраическое решение) удобнее написать программный код, который решит нашу задачу путем перебора многократных вычислений. Собственно, мы уже начали применять численные методы, начав использовать GeoGebra.

Для начала давайте сформулируем общее условие для любой подобной задачи: есть уравнение (система уравнений), корни которой нужно найти путём перебора. При этом стоит понимать, что корней может быть несколько. В нашем случае видно, что корень один и он принадлежит интервалу [1.0 ; 1.5]. Следовательно, мы можем ограничить диапазон поиска решения только этим отрезком.

Однако, в общем случае необходимо рассматривать практически бесконечный диапазон и максимально возможное количество корней. Именно поэтому мы и прибегли вначале к графическому решению в системе GeoGebra, определив количество корней и ограничив диапазон поиска каждого корня.

Теперь наша задача может быть сформулирована следующим образом: найти единственный корень уравнения, находящийся на заданном отрезке. Мы можем выполнить это, воспользовавшись простым перебором с заданным шагом, который обеспечит нам желаемую точность решения. Разумеется, не стоит рассчитывать на то, что при подобном переборе мы сможем найти точное решение (хотя для некоторых задач это возможно). Численными методами мы можем получить приближенное значение корня, точность этого решения зависит от величины шага прохождения по заданному отрезку (чем шаг меньше — тем точнее).

Определим необходимые переменные:
X_start — начальное значение интервала поиска по оси х,
X_end — конечное значение интервала поиска по оси х,
dX — шаг прохождения по интервалу поиска (по оси х),
X — текущая переменная, которая в начале равна X_start, а затем каждый раз увеличивается на значение переменной dX.

Подобный перебор удобнее всего выполнять в цикле For, в котором задать начало и конец диапазона, а также шаг изменения переменной X:

For X = X_start То X_end Step dX

Следует обратить внимание, что методом поиска корня является поиск точки пересечения функции с осью х (y = 0) — точки, где знак функции (разности функций) меняется на противоположный. Если на каком-то отрезке функция имеет единственный корень, то значение функции на концах этого отрезка будут иметь противоположные знаки. Где какой — зависит от того, убывающая функция или возрастающая.

В нашем примере значение функции (значение разности функций) слева меньше 0, следовательно, двигаясь слева направо нам нужно искать точку, где значение функции (разность функций Y — G) станет больше 0.

' Задаем начальные значения переменных:

X_start = 1 ' начало отрезка

X_end = 1.5 ' конец отрезка

dX = 0.0001 ' шаг по оси х

' Выполняем поиск корня в цикле

For X = X_start То X_end Step dX ' проходим наш интервал по оси х с заданным шагом

Y = 2*X*X*X + X*X - X ' вычисляем значение первой функции

G = 5 - X ' вычисляем значение второй функции

If Y - G > 0 Then ' если знак изменился, то корень найден!

GoTo End ' выходим из цикла

EndIf

EndFor

' Выводим полученные результаты

End:

TextWindow.WriteLine("Найдена точка пересечения с координатами: x = " + X + " y = " + 5-x)

Вот так — пусть не слишком оптимально, зато просто и всего за 12 строк кода решается эта задача на языке MS SmallBasic. Вы можете скопировать этот код в любую среду разработки SmallBasic, запустить и получить результат:

Найдена точка пересечения с координатами: x = 1.2094 y = 3.7906

Неоптимальность данного решения заключается в том, что программа вынуждена проходить весь интервал с  одним, заданным нами минимальным шагом. То есть, для нахождения этого ответа программа должна повторить вычисления 2095 раз. И стоит уменьшить шаг для увеличения точности (в 10 раз), как количество повторений цикла возрастет до 20937, что займет уже несколько секунд (а то и десятков секунд!). При следующем увеличении точности мы уже рискуем получить время вычисления, измеряемое минутами…

Для оптимизации (и ускорения вычислений) можно воспользоваться методом постепенного уменьшения шага по оси х с сокращением интервала поиска. Допустим, при при первом проходе мы воспользуемся значением шага в 1/10 нашего интервала. Тогда, найдя точку изменения знака, разделим шаг на 10, а интервал сократим так, чтобы он начинался в точке, предшествовавшей той, в которой знак изменился. Повторяя подобные операции несколько раз, мы довольно быстро найдем корень с очень высокой точностью.

Изменение шага в 10 раз предпочтительнее, так как мы работаем в десятичной системе счисления, и каждое изменение добавляет нам 1 разряд точности. Для двоичной системы предпочтительнее деление пополам — так называемый метод «бисекции» или «дихотомии». Что это такое — вы можете почитать в справочниках по математике. На Википедию — даже ссылку давать не хочется, потому что этот сайт стал откровенной информационной помойкой, в частности в вопросах физики, математики и прочих точных наук. Статьи для Википедии сейчас просто нагло выдирают из книг, не объясняя сопутствующих терминов, и делая кучи ошибок. Поэтому мы советуем самостоятельно искать хорошие книги или простые статьи.

Теперь наша обобщенная и расширенная задача разбивается на ряд подзадач:

1. Определить знак функции на левом конце интервала.
2. Проверить наличие корня в заданном интервале.
3. Задать шаг прохождения интервала.
4. Найти точку изменения знака.
5. Проверить совпадение шага с заданной точностью поиска.
6. Задать новые концы интервала: точка изменения знака и предшествующая ей точка.
7. Уменьшить шаг прохождения интервала.
8. Перейти к пункту 4.

Эти шаги алгоритма необходимо выполнять до достижения заданной точности. После этого мы можем вывести полученный результат.

Запишем наши функции:

y(x) = 2x³ + x² — x

и

g(x) = 5 — x

для поиска решения в виде

y(x) = g(x)
2x³ + x² — x = 5 — x
2x³ + x² — x — 5 + x = 0
2x³ + x² — 5 = 0

Таким образом, наша функция будет иметь вид:

f(x) = 2x³ + x² — 5

Зададим значения концов отрезка, полученные в результате анализа графика функции:

X_start = 1 ' начало отрезка

X_end = 1.5 ' конец отрезка

и требуемую точность:

Accuracy  = 0.00000001 ' желаемая точность

И начнем с Пункта 1. Знак функции на левом конце отрезка определим следующим образом: вычислим значение функции в этой точке и разделим на модуль получившегося числа (в MS SmallBasic это функция Math.Abs()). Если получится 1, знак — «+», если -1 , то знак «-«. На самом деле мы просто запомним получившееся значение и будем использовать его как знаковый множитель.

Sign = (2*X_start*X_start*X_start+X_start*X_start-5)/Math.Abs(2*X_start*X_start*X_start+X_start*X_start-5) ' знаковый множитель для начала отрезка

Пункт 2. Чтобы проверить наличие корня в заданном интервале нужно вычислить значения функции на концах отрезка и перемножить их. Если получится отрицательное число («+» на «-«) — на этом отрезке есть нечетное количество корней (в том числе — 1 корень), если положительное — количество корней на отрезке четное (или их там совсем нет). В нашем случае будем считать, что мы провели предварительный анализ функции и определили, что на заданном отрезке может быть не более одного корня.

If (2*X_start*X_start*X_start+X_start*X_start-5)*(2*X_end*X_end*X_end+X_end*X_end-5) > 0 Then ' корней нет 

Пункт 3. Шаг прохождения интервала будем рассчитывать как длину интервала делённую на 10.

dX = (X_end - X_start)/10

Пункт 4. Теперь вспомним код, который мы уже использовали, изменив его для одной результирующей функции:

For X = X_start То X_end Step dX ' проходим наш интервал по оси х с полученным шагом dX

Y = 2*X*X*X + X*X - 5 ' вычисляем значение функции

If Y * Sign < 0 Then ' если знак изменился, то мы ушли за корень

GoTo End ' тогда выходим из этого цикла

EndIf

EndFor

Пункт 5. Проверяем достижение желаемой точности поиска:

If dX <= Accuracy Then  ' желаемая точность достигнута

Пункт 6. Задаем новые концы уменьшенного интервала:

X_end = X

X_start = X - dX

Пункт 7. Изменяем шаг прохождения интервала:

dX = dX / 10

Наша новая программа готова:

X_start = 1 ' начало отрезка

X_end = 1.5 ' конец отрезка

Accuracy  = 0.00000001 ' желаемая точность

Sign = (2*X_start*X_start*X_start+X_start*X_start-5)/Math.Abs(2*X_start*X_start*X_start+X_start*X_start-5) ' знаковый множитель для начала отрезка

If (2*X_start*X_start*X_start+X_start*X_start-5)*(2*X_end*X_end*X_end+X_end*X_end-5) > 0 Then ' если вдруг корней на отрезке нет 

TextWindow.WriteLine("На заданном отрезке корней функции нет!") ' сообщаем

Program.End() ' и завершаем программу

EndIf

dX = (X_end - X_start)/10 ' определяем шаг

Start:

For X = X_start To X_end Step dX ' проходим наш интервал по оси х с полученным шагом dX

Y = 2*X*X*X + X*X - 5 ' вычисляем значение функции

If Y * Sign < 0 Then ' если знак изменился, то мы ушли за корень

GoTo Next ' тогда выходим из этого цикла

EndIf

EndFor

Next:

If dX <= Accuracy Then  ' желаемая точность достигнута

GoTo End ' переходим к выводу результата

EndIf

X_end = X ' меняем правую границу отрезка

X_start = X - dX ' меняем правую границу отрезка

dX = dX / 10 ' меняем шаг

GoTo Start ' переходим к началу цикла с новыми значениями

End:

TextWindow.WriteLine("Найден корень уравнения: x = " + X)

И даже при том, что точность в ней увеличена на 4 порядка (в 10000 раз), работает она практически мгновенно — за доли секунды. Вот результат:

Найден корень уравнения: x = 1.20935514

Согласитесь, это впечатляюще! И для этого нам пришлось написать всего 25 строк программного кода. При этом наша программа — практически универсальна. Не составляет большого труда изменить её так, чтобы она считала корень любой другой функции. Для этого достаточно изменить саму функцию (Пункты 1 и 2 и в цикле — Пункт 4) и границы интервала, в котором будем искать корень. Если функция имеет несколько корней, достаточно графически определить их примерное местоположение (точки пересечения с осью х) и затем, последовательно задавая интервалы поиска, вычислить их значения.

Итоги:

1. Если задачу можно решить аналитически, то лучше всего решить её аналитически. Это будет нагляднее и точнее. Кроме того, это тренирует мозг и разгружает вычислительные мощности устройства, на котором выполняется ваша программа. Простое решение сделает код более быстрым и оптимальным.
2. Никогда не стоит пренебрегать средствами графического решения задач. Это позволяет понять поведение функции, количество корней и получить их приблизительные значения.
3. Есть задачи, которые либо не решаются аналитически, либо для такого решения необходимо затратить много сил и времени. В этом случае лучше всего использовать именно численные методы, которые дадут вам числовое значение коря сложного нелинейного уравнения, отыскав решение с нужной точностью за приемлемое количество шагов.
4. В любом случае стоит задумываться над оптимизацией алгоритма, но стоит помнить, что эта задача тоже потребует сил и времени.

Поделиться: 

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