Лекція. Проектування напівсуматора і повного двійкового суматора

End.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

. (1.4)

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

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

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

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

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

Пример 1.17. (схема Горнера). Пусть необходимо вычислить значение многочлена Р_n (х) = a₀ + a₁ x + a₂ x² + … + a_n xⁿ при известных коэффициентах и заданном х. Если вычислять многочлен непосредственно по данной формуле, причем степени находить последовательным умножением на х, то потребуется выполнить 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);

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

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

, (1.5)

называемой алгоритмом Герона (см. формулу 1.4 из примера 1.16). Известно, что данный итерационный метод сходится при любом начальном приближении х⁽⁰⁾ > 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. Методы статистических испытаний (методы Монте-Карло). Это – методы, основанные на имитации случайных величин. Они могут оказаться незаменимыми при моделировании сложных объектов, но их изложение выходит за рамки дисциплины “Вычислительная математика”. Их подробному изучению посвящен, в частности, курс “Моделирование систем”.

Дата добавления: 2014-01-11