ПОИСК Статьи Чертежи Таблицы Численные методы одновариантного анализа в САПР из "Основы теории и проектирования САПР " К инвариантному МО одновариантного анализа относятся методы и алгоритмы для решения систем линейных и нелинейных алгебраических уравнений (НАУ), обыкновенных дифференциальных уравнений. Использование для этого библиотечных стандартных программ операционных систем ЭВМ в большинстве случаев неэффективно, так как в этих программах не учитываются особенности ММ объектов проектирования в САПР (высокая размерность систем, разреженность матриц в моделях, жесткость систем ОДУ, умеренные требования к точности анализа и др.). [c.34] Методы и алгоритмы решения систем ЛАУ с разреженными матрицами. Большинство задач одновариантного анализа сводится к решению систем ЛАУ, поэтому очень важно тщательно выбирать метод и отрабатывать алгоритм для решения этих систем. [c.34] Численные методы решения системы (2.13) разделяются на итерационные и прямые (точные). [c.34] Метод линейный и стационарный потому, что Н и С не зависят от номера итерации и от X. Порядок метода определяется количеством предыдущих значений X (на итерациях к, к—1), к—2),. ..), используемых в данном методе (в (2.14) присутствует одно X на к-й итерации). [c.35] Введем вектор погрешности (ошибки) на й-й итерации Е = - Х,-Х. Можно показать, что 1 Е, ЦН Ео , где ЦЕ , Н -соответствующие векторные и матричные нормы. Следовательно, Н определяет, во сколько раз была уменьшена норма ошибки после к итераций, т. е. скорость сходимости. [c.35] 15) и (2.16) следует, что вектор приращений можно использовать в качестве критерия окончания итераций, но при р(Н)- 1 применяют соотношение (2.16) и оценивают М (Н). [c.36] Прямые м етоды решения системы (2.13) основаны главным образом на использовании методов Гаусса или У-разложения при условии, что в ходе решения в оперативной памяти хранятся только ненулевые элементы (ННЭ) и вычисления проводятся только с ними. В этом случае разработка прямых методов связана с решением задач выбора способа хранения разреженных матриц, разработки стратегии выбора главного элемента с целью сохранения разреженности и точности решения (2.13) оценки точности полученных результатов. [c.36] Обратный ход заключается в последовательном определении неизвестных, начиная с Хп = Ь п/ипп и заканчивая х Элемент аьк.и является главным элементом на к-м шаге исключения. Учет разреженности матрицы А основан на следующих принципах 1) хранятся только ННЭ матрицы А 2) формула (2.17) используется только, если йгк.кфО и аи,-,кФО-, 3) количество вторичных ненулевых элементов (ВНЭ), возникающих, если ац,к—0, а ац,к+1фО, должно быть минимальным. [c.37] Для хранения разреженных матриц применяются следующие способы прямой, упорядоченных и связанных списков. В первом способе для каждого ННЭ запоминаются числа ац, 1 и /. Этот способ применяется при вводе исходной матрицы, но неудобен для реализации метода Гаусса. Поэтому после ввода исходных данных переходят к другим способам хранения матрицы А, При хранении матрицы А с использованием упорядоченных списков ННЭ располагаются по строкам в соответствии с основным алгоритмом метода Гаусса. Вводятся дополнительные одномерные массивы указателей длиной п для хранения столбцовых и строчных индексов главных элементов, необходимых для выполнения прямого хода. Новые ВНЭ добавляются к строчно-упорядоченному и столбцовоупорядоченному спискам в процессе прямого хода. Это требует дополнительных затрат памяти и времени ЭВМ и процедур по сжатию информации. При хранении матрицы А с использованием связных списков ННЭ располагаются произвольно. В массивах указателей для каждого ННЭ хранятся адреса следующих элементов в той же строке и в том же столбце. Добавление нового ВНЭ в /-ю строку и /-Й столбец сводится к выборке первого элемента свободного списка и установке соответствующих связок, что значительно проще, чем в предыдущем способе. Основной недостаток этого способа — в ходе исключения нужны дополнительные вычисления на поиск главного элемента. [c.37] Если при решении системы (2.13) возникла погрешность Аац,к в вычислении коэффициента матрицы А, то она может быстро возрастать, приводя к ошибкам результата Ах1х= А.ац1ац, где г=гпах Яг /т1п Хг —число обусловленности матрицы А кг — собственные числа матрицы А. При плохо обусловленной матрице А ошибка в решении может оказаться значительной, поэтому алгоритм выбора главного элемента дополняется следующим условием. Вводится множество элементов с, для которых Мц,к=Ми, и удовлетворяется условие численной устойчивости. В качестве главного элемента на к-м шаге выбирается наибольший по модулю из кандидатов, находящихся в сь. Для контроля точности полученного решения находят вектор невязки R=B—АХ. Если норма К мала, а система хорошо обусловлена, то решение найдено достаточно точно. В противном случае решение можно уточнить итерационным методом. [c.38] Алгоритм итерационного уточнения рассмотрим для случая, когда все главные элементы располагаются последовательно на диагонали матрицы А. Для организации итераций необходимо найти нижнетреугольную матрицу Ь, диагональные элементы которой равны 1 и выполняется равенство А=Ы1. Элементы матрицы Ь определяются в процессе прямого хода Гаусса по формуле /,4,А=—аг, й/аАМ, 1= +1, -Ь2. . [c.38] Критерий окончания итераций Хт+1—Х У е Хш+111, где е — машинная точность. Для плохо обусловленных матриц сходимость может быть медленной, в этом случае необходимо оценить число обусловленности g по упрощенным алгоритмам. Если g имеет порядок, обратный машинной точности, то нужно перейти на вычисления с повышенной разрядностью. Во многих случаях эффективно сочетание метода Гаусса и итерационного уточнения. При этом вводится ограничение Опор на абсолютную величину элементов ац, йц,и, 1гк,к- Если значение элемента меньше абсолютного значения Опор, то он заменяется нулем (естественный порог апор —е] ,/], обычно апор=0.01). По методу Гаусса получается приближенное решение, которое затем уточняется по (2.18). [c.39] Особенность метода состоит в том, что в ближайшей окрестности решения X всегда выполняются условия сходимости итераций 1. Для практической реализации метода необходимо решить задачи выбора критерия окончания итераций, способа вычисления матрицы Я , обеспечения сходимости метода от заданного начального вектора Хо. [c.40] Элементы матрицы Якоби можно вычислять аналитически и численно. Практика показала, что метод Ньютона наиболее эффективен при аналитическом вычислении элементов. Численное дифференцирование соответствует дискретному методу Ньютона, который в общем случае не обладает квадратичной скоростью сходимости итераций. [c.40] Основные методы обеспечения сходимости итераций при заданном начальном векторе Хо — продолжения по параметру и дифференцирования по параметру. [c.40] Точность промежуточных вычислений X (i,) можно задавать невысокой (обычно выполняется 1—2 итерации), выполняя с высокой точностью только последние итерации при =1. [c.41] Система (2.22) решается простейшими методами интегрирования (обычно явным методом Эйлера). Интегрирование (2.22) завершается циклом итераций по Ньютону от начальных условий Хо=Х(1). [c.41] Основные требования, предъявляемые к методу интегрирования системы (2.23), — универсальность, надежность, точность и экономичность. Выполнить эти требования в рамках одного метода невозможно, поэтому разработан ряд базовых методов различной степени точности и экономичности, применяемых в зависимости от особенностей решаемой задачи. При выборе базовых методов основными критериями являются точность, устойчивость и экономичность. Основные проблемы, возникающие при алгоритмической реализации методов, — обеспечение сходимости при решении системы НАУ, которая получается на каждом шаге Л после подстановки (2.24) в (2.23) контроль точности и устойчивости интегрирования автоматический выбор шага Л для минимизации вычислительных затрат. [c.42] Вернуться к основной статье