Классификация численных методов

С некоторой степенью условности все численные методы можно разбить на следующие классы:

1) методы эквивалентных преобразований;

2) методы аппроксимации;

3) прямые методы;

4) итерационные методы;

5) методы статистических испытаний (методы Монте-Карло)

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

1. Методы эквивалентных преобразований. Эти методы основаны на замене исходной задачи другой, имеющей то же решение, но решающейся существенно проще.

Пример 1.12. Эквивалентное преобразование приведенного квадратного уравнения x² + px + q = 0 с помощью выделения полного квадрата к виду сводит задачу к проблеме вычисления квадратного корня и приводит к известным формулам (1.1).

Эквивалентные преобразования иногда позволяют свести решение исходной вычислительной задачи к решению задачи совершенно иного типа.

Пример 1.13. Задача отыскания экстремума функции y = f(x) сводится к решению уравнения f ’ (x) = 0.

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

Пример 1.14. Учитывая определение производной , для ее приближенного вычисления можно использовать формулу , где h – параметр приближенной формулы. Погрешность аппроксимации стремится к нулю при h ® 0.

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

Пример 1.15. Требуется приближенно вычислить значение , а > 0 на ЭВМ, способной выполнять лишь простейшие арифметические операции. По определению х является положительным корнем уравнения х² – а = 0. Пусть х⁽⁰⁾ – некоторое начальное приближение к . Заменим параболу у = х² – а прямой, касающейся параболы в точке х = х⁽⁰⁾. Уравнение этой прямой: у = (х⁽⁰⁾)² – а + 2 х⁽⁰⁾×(х – х⁽⁰⁾). Точа пересечения этой касательной с осью Ох дает лучшее, чем х⁽⁰⁾ приближение к решению и находится из линейного уравнения 0 = (х⁽⁰⁾)² – а + 2 х⁽⁰⁾×(х – х⁽⁰⁾). Решая его, получим приближенную формулу

. (1.4)

Вычислим , взяв х⁽⁰⁾ = 1.5. Получим по формуле (1.4) при точном значении 1.4142….

3. Прямые методы. Метод решения задачи называется прямым, если после выполнения конечного числа элементарных операций он позволяет получить решение, которое при отсутствии ошибок округления будет точным.

Примером прямого метода может служить поиск корней приведенного квадратного уравнения по формулам (1.1).

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

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

Пример 1.16. (схема Горнера). Пусть необходимо вычислить значение многочлена Р_n (х) = a₀ + a₁x + a₂x² + … + a_nxⁿ при известных коэффициентах и заданном х. Если вычислять многочлен непосредственно по данной формуле, причем степени находить последовательным умножением на х, то потребуется выполнить 2n – 1 умножений и n сложений.

Значительно более экономным является метод, называемый схемой Горнера. Он основан на записи многочлена в следующем эквивалентном виде:

Р_n (х) = ((…((a_n x + a_n–1) x + a_n–2) x + …) x + a₁) x + a₀.

Данную запись легко реализовать программно с помощью следующего фрагмента

Var a: array[0..n] of real;

begin readln(a[0],…, a[n]);

Readln(x);

p:= a[n];

for j:= n – 1 downto 0 do

p:= p*x + a[j];

Writeln(p);

End.

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

Пример 1.17. Требуется приближенно вычислить значение , а > 0 на ЭВМ, способной выполнять лишь простейшие арифметические операции. Пусть х⁽⁰⁾ – некоторое начальное приближение к . Для вычисления каждого следующего приближения построим рекуррентную формулу:

, (1.5)

называемой алгоритмом Герона (см. формулу 1.4 из примера 1.15). Известно, что данный итерационный метод сходится при любом начальном приближении х⁽⁰⁾ > 0, так что область его сходимости – множество всех положительных чисел.

Вычислим с его помощью с точностью до 8 значащих цифр, взяв х⁽⁰⁾ = 1.5. Последовательно получим х⁽¹⁾ = 1.4166667; х⁽²⁾ = 1.4142157; х⁽³⁾ = 1.4142136; х⁽⁴⁾ = 1.4142136. У двух последних приближений совпали первые 8 цифр, следовательно, х = 1.4142136 можно считать решением задачи.

Практическая реализация итерационных методов всегда связана с необходимостью выбора критерия окончания итерационного процесса. Вычисления не могут продолжаться бесконечно долго и должны быть прерваны в соответствии с некоторым критерием, связанным, например, с достижением заданной точности. Для формирования такого критерия, как правило, используются так называемые апостериорные оценки погрешности – неравенства, в которых величина погрешности оценивается через известные или получаемые в процессе вычислений величины. Например, для итерационного процесса (1.5) справедлива следующая оценка: , позволяющая оценивать абсолютную погрешность k-го приближения через значения двух последних приближений. Эта оценка дает простой критерий окончания процесса при заданной точности e: как только окажется выполненным неравенство

|x^(k) – x^(k–1) | < e, (1.6)

следует прекратить вычисления и принять x^(k) за решение задачи.

В общем случае в критерии окончания могут использоваться либо некоторые значения аргумента, либо значения вычисляемой функции. В первом случае говорят, что критерием является достигнутая точность по аргументу, во втором – точность по функции. Например, критерий (1.6) определяет точность по аргументу. В качестве критерия точности по функции, например, при решении уравнения f(x) = 0 можно использовать неравенство |f(x^(k))| < e. Для примера 1.17 это будет неравенство .

5. Методы статистических испытаний (методы Монте-Карло). Это – методы, основанные на имитации случайных величин. Они могут оказаться незаменимыми при моделировании сложных объектов, но их изложение выходит за рамки дисциплины “Вычислительная математика”. Их подробному изучению посвящен, в частности, курс “Моделирование систем”.

 

КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАДАНИЯ

1. Приведите примеры прямых методов, известных Вам, например, из курса школьной или высшей математики.

2. Составьте два варианта программы алгоритма Герона с разными критериями достижения заданной точности 10^–6 – по функции и аргументу. Вычислите с помощью этих программ значение .

 

Тема 2. Прямые методы линейной алгебры

Модификации метода Гаусса

При решении системы уравнений

простейшим вариантом метода Гаусса имеют место большие погрешности. Причина заключается в появлении больших коэффициентов, при округлении которых получается большая абсолютная погрешность D ~ 0.5. В свою очередь, большие коэффициенты получаются после деления на маленький ведущий коэффициент .

Вывод: для уменьшения влияния ошибок округления надо выбирать ведущий элемент не просто отличный от 0, но и достаточно большой.

Первая модификация метода Гаусса – поиск по строкам. В алгоритме ведущий элемент надо выбирать из условия .

Недостаток модификации. Предположим х_i найден с погрешностью D. Тогда при поиске какого-либо х_s надо, согласно формуле обратного хода, умножать . При этом погрешность D также умножится на . Если значение велико, то погрешность возрастет.

Вывод: надо обеспечить, чтобы ведущий элемент был не просто большим, а самым большим по модулю в своей строке. Тогда при нормировке ведущей строки все прочие коэффициенты, согласно формуле (5), будут по модулю меньше 1, и ошибки будут уменьшаться.

Вторая модификация метода Гаусса – поиск по столбцам. Указанное требование можно обеспечить, если неизвестные х_i исключаются в произвольном порядке, а в ведущей строке ищется , доставляющий . Это и будет очередной ведущий элемент. После определения ведущего элемента меняем местами k-й и r-й столбцы.

Внимание. При такой замене меняется нумерация неизвестных x_i. Чтобы обеспечить такую замену, надо при программировании ввести массив p₁,…p_n с настоящими номерами неизвестных. В начале прямого хода все p_i = i – обычная нумерация. После нахождения ведущего элемента меняем местами p_k и p_r. При обратном ходе по формуле (7) вычисляются перенумерованные x_i. После вычисления всех неизвестных надо положить y[p[i]]:=x[i], и массив y[i] будет окончательным решением задачи.

Третья модификация метода Гаусса – полный поиск. В качестве ведущего выбирается элемент , доставляющий . При этом меняются местами k-й и r-й столбцы, p_k и p_r, а также m-я и k-я строки. Эта модификация обеспечивает максимальную точность, но и наиболее сложна.