Лекция №4 Вычислительные операции при решении прикладных инженерных задач

Теоретические вопросы:

4.1. Вычисления и САПР

4.2. Алгоритмизация математических моделей

4.3. Точность вычислительных операций

4.1. Вычисления и САПР

Вычислительную задачу или некоторую ее подзадачу можно представить в виде операторных соотношений

, (4.1)

или

(4.2)

При этом T и X представляют собой в обобщенном виде соответственно исходные данные и искомый ответ; полагаем, что , причем пространства S и Q надлежащим образом метризованы или нормированы. Операторы A или B определяются условиями задачи; иногда входные параметры могут выступать как коэффициенты в операторах A или B.

Соотношение (4.1) обычно называют прямой операторной задачей, а (4.2) – обратной задачей, или операторным уравнением.

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

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

1. внутренний алгоритм;

2. макроконструкции;

3. внешний алгоритм с интерфейсом;

4. передача геометрических данных;

5. перенос геометрических данных;

6. автономные вычисления.

Лучшие из известных внутренних алгоритмов решения различного рода уравнений и их систем в настоящее время уже запрограммированы и включены в стандартные библиотечные программы. Такие программы часто называют решателями (solvers). Но главной задачей по-прежнему остается выбор программы решения. Размерность задачи и цели математического моделирования ставят перед выбором между прямым и итерационным методом решения. Используемые на практике прямые методы решения систем уравнений обычно состоят из двух процедур, первая из которых выполняет приведение матрицы системы к треугольному виду последовательным исключением или факторизацией, а вторая – выполняет обратную подстановку. Точность решения, полученная прямым методом может быть значительно улучшена сравнительно небольшими дополнительными вычислениями – посредством итерационного улучшения или уточнения.

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

(4.3)

Оператор P учитывает первоначальные или преобразованные условия задачи, а также исходные данные. Решение задачи теперь состоит в отыскании неподвижной точки X* оператора P. Для этого задают начальное приближение X0 и строят последовательность приближений

(4.4)

При определенных условиях эта последовательность сходится к ответу X*. По сравнению с прямыми методами итерационные имеют следующие преимущества:

1. значительно проще для программирования;

2. могут эффективно справляться с разреженными матрицами, сохраняя и обрабатывая только ненулевые элементы;

3. требуют меньше оперативной памяти.

Среди наиболее широко применяемых итерационных методов особо выделяются:

1. методы Якоби и Гаусса-Зейделя;

2. точечные итерационные методы;

3. метод последовательной верхней релаксации (SOR);

4. метод Ричардсона;

5. полуитерационные методы.

Наиболее часто используются методы Якоби и Гаусса-Зейделя являются наиболее простыми из многочисленного семейства этих алгоритмов. Однако их свойства и особенности применения достаточно типичны. Главной отличительной чертой всех итерационных процедур является зависимость самой возможности получения решения т свойств итерационной матрицы S, которая интегрирует свойства матрицы задачи и свойства метода.

Так, для метода Якоби матрица S и вектор имеют вид:

(17)

где D – диагональная матрица, сформированная из диагональных элементов матрицы А.  "Малость" матрицы S в этом случае, как видно из (17), предполагает хорошую аппроксимацию матрицы системы диагональной матрицей, или матрицей  с диагональным преобладанием. Заметим в этой связи, что для задач с симметричными и положительно определенными матрицами с диагональным преобладанием можно строго доказать сходимость процедуры Якоби. 

Для метода Гаусса-Зейделя:

Итерационная матрица S и вектор могут быть представлены в виде

()

где – матрица, сформированная из элементов нижнего треугольника матрицы А. В этом случае "малость" S реализуется при близости матрицы A к нижней треугольной матрице . Отсюда следует, что можно ожидать хорошую сходимость процедуры Гаусса-Зейделя для "почти" нижне-треугольных матриц. Однако эти признаки носят исключительно качественный характер и не являются условиями сходимости.

4.2. Алгоритмизация математических моделей

При проведении вычислительного эксперимента исходная математическая модель проектируемого технического объекта претерпевает ряд преобразований, необходимых для того, чтобы количественный анализ был осуществлен при помощи ЭВМ. Эти преобразования, в конечном счете, должны привести к такому алгоритму, который можно было бы реализовать на ЭВМ, т.е. составить ЭВМ-программу в виде последовательности элементарных действий (арифметических и логических операций), реализуемых командами ЭВМ. Наиболее удобными математическими моделями с точки зрения реализации на ЭВМ являются линейные математические модели в виде квадратной системы линейных алгебраических уравнений (СЛАУ)

(4.5)

где A – матрица СЛАУ порядка N; x – вектор, включающий N искомых фазовых переменных рассматриваемого технического объекта; b – вектор правой части СЛАУ.

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

Эти операции можно условно расположить на трех уровнях иерархии. На нижнем уровне находятся операция сложения векторов, состоящая из скалярных операций сложения их координат, и операция скалярного умножения векторов, состоящая из скалярных операций умножения двух сомножителей и сложения полученных результатов. Операция умножения матрицы на вектор составлена из серии скалярных умножений, и такую операцию следует отнести к более высокому уровню иерархии. Наконец, умножение матриц состоит из серии умножений матрицы на вектор. Перечисленные операции можно осуществлять различными способами, и в зависимости от структуры векторов и матриц среди этих способов может быть найден наиболее рациональный с точки зрения производительности ЭВМ. Объем вычислительной работы, выполняемой ЭВМ-программой, измеряют количеством операций сложения или умножения чисел с плавающей точкой (или запятой), или флопов. Так, например, каждая из выполняемых процедур умножения матрицы на вектор требует выполнения N=2mn флоп. Умножение матрицы A размера m x n на матрицу B размера n x r должно в общем случае потребовать 2mnr флоп. Если учитывать конкретную структуру матриц, то это число можно существенно сократить. В вычислениях с матрицами больших размеров наряду с экономией арифметических операций актуальной является и экономия памяти ЭВМ, используемой для хранения исходных матриц и записи результатов вычислений. Вопрос использования памяти особенно важен, поскольку память современных ЭВМ организована по иерархическому принципу. Процессору, выполняющему арифметические операции, требуется наименьшее время для обращения к так называемой кэш-памяти (буферной памяти между регистрами центрального процессора и основной частью оперативной памяти).

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

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

Таким образом, можно дать следующие общие рекомендации выбора метода решения систем уравнений:

1. для небольших задач целесообразно использовать наиболее удобные стандартные программы, основанные, как правило, на прямых методах;

2. для задач средних размеров следует выбирать прямой метод;

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

4.3 Точность вычислительных операций

При выборе и применении метода решения системы линейных алгебраических уравнений важно учитывать не только требования к объему памяти и времени вычислений, но и нельзя игнорировать точность. Количество вычислительных операций метода влияет на точность решения (посредством ошибок аппроксимации и округления), так и на время и стоимость вычислений. Обычно вычислительная машина выполняет арифметические операции, используя заданную длину слова для каждого числа. Для объяснения примем десятичную запись чисел, хотя обычно числа хранятся не в десятичной форме, а, например, в двоичной или восьмеричной.

Предположим, что длина слова в вычислительной машине равна 10 значащим цифрам и выполняются действия с числами 685378,9879 и 43789б,4879. Простое сложение этих чисел дает 1123275,4758, но так как можно записать лишь 10 десятичных чисел, то вычислительная машина запишет в качестве суммы 1123275,475 или 1123275,476 в соответствии с используемым правилом округления. И в том, и в другом случаях произойдет потеря существенной информации, и вносимые ошибки сложным образом будут увеличиваться в последующих вычислениях. Предположим, что к предыдущей сумме должно быть прибавлено число 111111,1111. Прибавление 111111,1111 к 1123275,475 дает 1234386,586 как при усечении, так и при округлении. Аналогично, прибавление 1123275,476 к 111111,1111 дает 1234386,587. Чтобы получить точное значение суммы, нужно прибавить 111111,1111 к 11-значной форме предыдущей суммы, в результате чего получается 1234386,5869. Необходимое заметить, что округление дает приближенный результат, более близкий к точному значению, чем усечение, но оба содержат ошибку. Последующие операции сложения, вычитания, умножения или деления приводят в результате усечения последовательно к ошибкам в девятом знаке, восьмом и так далее. При округлении будет происходить точно такой же процесс, но с меньшей скоростью.

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

Вопросы для самоподготовки:

1. Опишите основные вычислительные алгоритмы, применяемые в современных САПР?

2. Охарактеризуйте основы и приемы алгоритмизации математических моделей?

3. На что влияет точность вычислительных операций?