5.2. Некоторые вычислительные модели

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

1) на конкретных примерах научиться программированию;

2) заглянуть в "кухню" алгоритмов, используемых в пакете

Mcad, чтобы пользоваться ими сознательно.

5.2.1. Системы уравнений

В общем, в простейшей ситуации здесь можно воспользоваться кнопкой "Solve", блоками Given . . Find, Given . . Minerr, а также функциями Root, Polyroot (для многочленов), Lsolve (для линейных систем уравнений), обратной матрицей, обобщенной обратной матри-цей (Geninv), а в случае двух переменных функциями Slope, Intercept.

5.2.1.1. Системы линейных уравнений

В этом пункте будет обсуждаться самая популярная (после опти-мизации) задача решения системы линейных уравнений вида A x = b, где А – прямоугольная (чаще всего квадратная) матрица, х – искомый вектор, b – вектор (или матрица) правой части. Если А – квадратная матрица, а b – вектор, то задача легко решается либо использованием обратной матрицы (x = A^-1b), либо применением встроенной функции Lsolve(A, b), возвращающей вектор решения. Но заглянем поглубже.

А. Обыкновенная квадратная хорошо обусловленная (определи-тель матрицы А не слишком мал по сравнению с ее элементами) систе-ма уравнений. Ее можно легко решить методом Крамера и методом исключения Гаусса. Программирование метода Крамера довольно оче-

видно:

Cramer(A, b) := d  |A|

for k  0 .. Last(b)

C  A, C b

x _k  |C| ∙ d

x

Метод Гаусса удобно программировать для расширенной матрицы

C = (A, b), используя в одном проходе полное исключение (по типу

преобразования Жордана):

Gauss(A, b) := n  Last(b), C  Augment(A, b)

for i  0 .. n

p  C _{i,, i}^-1

for j  0 .. n + 1

C_{i, j}  C_{i, j} ∙ p

for k  0 .. n

if k ≠ i

p  C_{k, i} ,

for j  i .. n + 1

C_{k, j}  C_{k, j} – C_{i, j} ∙ p

C

B. В более сложных ситуациях необходимы специальные прие-мы. В самом деле, как правило Крамера, так и метод Гаусса для реше-ния системы уравнений с n неизвестными требуют порядка n³ ариф-метических операций. Для больших систем уравнений это довольно пессимистичная оценка (в задачах экономики решаются системы уравнений с сотнями и тысячами неизвестных). Кроме того, не всегда требуется предельная точность результата. Рассмотрим для примера (который позволяет лишь заглянуть в "кухню" методов вычислений) систему линейных уравнений Ax = b с доминирующей главной диа-гональю, т. е. с матрицей А такой, что | A _{i, i} | > | A _{i, j} | . Вве- дем матрицу Т _{i, j} = и вектор s _i = b _i / A _i,i . Тогда сис-тему уравнений можно записать в виде x = s - Tx . Так как в данном случае можно выбрать норму матрицы Т (ее можно оценить как мак-симальное значение суммы модулей элементов матрицы в каждой строке) меньше единицы, то итерационный процесс уточнения ре-шения x ^{(n + 1)} = s - Tx ⁽ⁿ⁾, x ⁽⁰⁾ = s, n = 0, 1, ... , будет сходиться к точно-

му решению исходной задачи (метод итераций). На каждой итерации требуется лишь порядка n² вычислений. Процесс можно оформить в

виде функции: