Определение числа операций алгоритма метода квадратного корня

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

1. Факторизация исходной матрицы, то есть вычисление матриц S и D:

;

2. Выполнение “обратного” хода:

;

3. Вычисление m раз значений квадратных корней.

Общее количество операций равно , или приблизительно , что практически в два раза меньше, чем число операций в алгоритме метода Гаусса.

Метод Якоби

Последнее выражение представим в виде итерационной схемы

, (2.9)

где n - номер итерации. Для получения решения используется следующий алгоритм. В качестве нулевого приближения выбираются какие-либо (зачастую произвольные) значения искомых величин, которые подставляются в правую часть выражения (2.9), что позволяет определить первое приближение неизвестных . Затем полученный результат вновь подставляется в правую часть выражения (2.9) и вычисляются , и так далее. Вычислительный процесс заканчивается, например, когда выполняется условие

,

где e > 0 - заданная точность вычисления результата.

Пример 2.3. Рассмотрим систему алгебраических уравнений

Точное решение этой системы x = 0,5, y=1,5.

Из первого уравнения выразим первую неизвестную x

,

а из второго - неизвестную y,

.

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

В качестве начального приближения примем . Результаты расчетов сведены в табл. 2.1. На рис. 2.1 графически показан ход выполнения итерационного процесса метода Якоби.

Таблица 2.1

Результаты выполнения итерационной процедуры метода Якоби

Представим матрицу коэффициентов А в виде суммы , где - нижняя треугольная матрица с нулевой диагональю; - верхняя треугольная матрица с нулевой диагональю; - диагональная матрица. Теперь систему уравнений Ax = f можно представить в виде:

и метод Якоби будет выглядеть следующим образом:

.

Учитывая, что , последнее выражение можно также представить в форме

. (2.10)

Y

4x + 2y = 5

3x + 5y = 9

0 X

0 1 2 3

Метод Зейделя

Преобразуем выражение (2.9) к виду

, (2.11)

где n - также номер итерации. В отличие от метода Якоби, теперь для вычисления очередной неизвестной используются найденные на этой же итерации значения всех предыдущих величин. Как и ранее, вычислительный процесс заканчивается, когда выполняется условие:

,

e>0 - заданная точность вычисления результата.

Пример 2.4. Рассмотрим систему алгебраических уравнений, указанную в предыдущем примере:

Представим полученные выражения в виде итерационной схемы:

Это означает, что для нахождения величины y на (n+1) итерации используется значение x, только что вычисленное на этой же итерации. В качестве начального приближения также примем . Результаты расчетов сведены в табл. 2.2. На рис. 2.2 графически показан ход выполнения итерационной процедуры Зейделя.

Как и в предыдущем случае, представим матрицу коэффициентов А в виде суммы с теми же обозначениями. Метод Зейделя можно представить в форме

.

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

. (2.12)

Таблица 2.2

Результаты выполнения итерационной процедуры метода Зейделя

Не нашли, что искали? Воспользуйтесь поиском: