Методы решения систем линейных алгебраических уравнений

⇐ ПредыдущаяСтр 35 из 50Следующая ⇒

В программах анализа в САПР для решения СЛАУ чаще всего применяют метод Гаусса или его разновидности. Метод Гаусса – метод последовательного исключения неизвестных из системы уравнений.

При исключении k–й неизвестной xk из системы уравнений

AX = B

все коэффициенты aij при i> k и j> k пересчитывают по формуле

a_ij = aij – aik akj / akk.

Исключение n–1 неизвестных, где n – порядок системы, называют прямым ходом, в процессе которого матрица коэффициентов приобретает треугольный вид. При обратном ходе последовательно вычисляют неизвестные, начиная с x_n.

В общем случае число арифметических операций для решения по методу Гауссу пропорционально n³. Это приводит к значительным затратам машинного времени, поскольку СЛАУ решается многократно в процессе одновариантного анализа, и существенно ограничивает сложность анализируемых объектов.

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

Матрицу называют разреженной, если большинство ее элементов равно нулю. Эффективность обработки разреженных матриц велика потому, что, во–первых, пересчет по формуле не требуется, если хотя бы один из элементов a_ik или akj оказывается нулевым, во–вторых, не требуются затраты памяти для хранения нулевых элементов. Хотя алгоритмы обработки разреженных матриц более сложны, но в результате удается получить затраты машинного времени, близкие к линейным, например, затраты оказываются пропорциональными n^{1, 2}.

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

а) б)

Рис.15.1. Матрицы коэффициентов для: а) — обычных; б) – разреженных матриц

Для пояснения этой зависимости рассмотрим два варианта представления одной и той же СЛАУ. В первом случае система уравнений имеет вид

a11x1 + a12x2 + a13x3 + a14x4 + a15x5 = b1;

a21x1 + a22x2 = b2;

a31x1 + a33x3 = b3;

a41x1 + a44x4 = b4;

a51x1 + a55x5 = b5.

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

Во втором случае меняются местами первое и пятое уравнения. Матрицы коэффициентов имеют вид рис.15.1, б, где ненулевые элементы представлены знаком «+». Теперь вторичные ненули не появляются, матрица остается разреженной, высокая вычислительная эффективность сохраняется.

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

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

Методом разряженных матриц называют метод решения СЛАУ на основе метода Гаусса с учетом разреженности (первичной и вторичной) матрицы коэффициентов.

Метод разреженных матриц можно реализовать путем интерпретации и компиляции. В обоих случаях создаются массивы ненулевых коэффициентов матрицы (с учетом вторичных ненулей) и массивы координат этих ненулевых элементов.

При этом выигрыш в затратах памяти довольно значителен. Так, при матрице умеренного размера 200х200 без учета разреженности потребуется 320 кбайт. Если же взять характерное значение 9 для среднего числа ненулей в одной строке, то для коэффициентов и указателей координат потребуется не более 28 кбайт.

Поскольку СЛАУ в процессе анализа решается многократно, то и операции поиска нужных коэффициентов также повторяются многократно, на что естественно тратится машинное время.

Способ компиляции более экономичен по затратам времени, но уступает способу интерпретации по затратам памяти. При компиляции поиск нужных коэффициентов выполняется однократно перед численным решением задачи. Вместо непосредственного выполнения арифметических операций для каждой из них компилируется команда с найденными адресами ненулевых коэффициентов. Такие команды образуют рабочую программу решения СЛАУ, которая и будет решаться многократно. Очевидно, что теперь в рабочей программе будет выполняться

минимально необходимое число арифметических операций.

Анализ в частотной области выполняется по отношению к линеаризованным моделям объектов. Для линейных СОДУ справедливо применение для алгебраизации дифференциальных уравнений преобразования Фурье, в котором оператор d/dt заменяется на оператор j.

Характерной особенностью получающейся СЛАУ является комплексный характер матрицы коэффициентов, что в некоторой степени усложняет процедуру решения, но не создает принципиальных трудностей. При решении задают ряд частот f_k. Для каждой частоты решают СЛАУ и определяют действительные и мнимые части искомых фазовых

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

Одновариантный анализ позволяет получить информацию о состоянии и поведении проектируемого объекта в одной точке пространства внутренних Х и внешних Q параметров. Очевидно, что для оценки свойств проектируемого объекта этого недостаточно. Нужно выполнять многовариантный анализ, т.е. исследовать поведение объекта, в ряде точек упомянутого пространства, которое для краткости будем далее называть пространство аргументов.

Чаще всего многовариантный анализ в САПР выполняется в интерактивном режиме, когда разработчик неоднократно меняет в математической модели те или иные параметры из множеств Х и Q, выполняет одновариантный анализ и фиксирует полученные значения выходных параметров. Подобный многовариантный анализ позволяет оценить области работоспособности, степень выполнения условий работоспособности, а следовательно, степень выполнения технического задания (ТЗ) на проектирование, разумность принимаемых промежуточных решений по изменению проекта и т.п.

Областью работоспособности называют область в пространстве аргументов, в пределах которой выполняются все заданные условия работоспособности, т.е. значения всех выходных параметров находятся в допустимых по ТЗ пределах.

Среди процедур многовариантного анализа можно выделить типовые, выполняемые по заранее составленным программам. К таким процедурам относятся анализ чувствительности и статистический анализ. Наиболее просто анализ чувствительности реализуется путем численного дифференцирования. Пусть анализ проводится в некоторой точке Хном пространства аргументов, в которой предварительно проведен одновариантный анализ и найдены значения выходных параметров yj ном. Выделяется N параметров–аргументов хi (из числа элементов векторов X и Q), влияние которых на выходные параметры подлежит оценить, поочередно каждый из них получает приращение xi, выполняется одновариантный анализ, фиксируются значения выходных параметров yj и подсчитываются значения абсолютных

Aji = (yj – yj ном ) / xi

и относительных коэффициентов чувствительности

Bji = Aji xiном / yjном.

Такой метод численного дифференцирования называют методом приращений. Для анализа чувствительности, согласно методу приращений, требуется выполнить N+1 раз одновариантный анализ. Результат его применения – матрицы абсолютной и относительной чувствительности, элементами которых являются коэффициенты Aji и Bji.

Анализ чувствительности – это расчет векторов градиентов выходных параметров, который входит составной частью в программы параметрической оптимизации, использующие градиентные методы.

Цель статистического анализа – оценка законов распределения выходных параметров и (или) числовых характеристик этих распределений. Случайный характер величин yj обусловлен случайным характером параметров элементов xi, поэтому исходными данными для статистического анализа являются сведения о законах распределения xi. В соответствии с результатами статистического анализа прогнозируют такой важный производственный показатель, как процент бракованных изделий в готовой продукции (рис.15.2.).

Рис.15.2. Кривая нормального распределения

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

В САПР статистический анализ осуществляется численным методом – методом Монте–Карло (статистических испытаний). В соответствии с этим методом выполняются N статистических испытаний, каждое статистическое испытание представляет собой одновариантный анализ, выполняемый при случайных значениях параметров–аргументов. Эти случайные значения выбирают в соответствии с заданными законами распределения аргументов x_i.

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

– гистограммы выходных параметров;

– оценки математических ожиданий и дисперсий выходных параметров:

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

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

Более типична ситуация, когда законы распределения x_i неизвестны, но с большой долей уверенности можно указать предельно допустимые отклонения Δ x_i параметров x_i от номинальных значения xiном (такие отклонения часто указываются в паспортных данных на комплектующие детали). В таких случаях более реалистично применять метод анализа на наихудший случай. Согласно этому методу, сначала выполняют анализ чувствительности с целью определения знаков коэффициентов чувствительности. Далее осуществляют m раз одновариантный анализ, где m – число выходных параметров. В каждом варианте задают значения аргументов, наиболее неблагоприятные для выполнения условия работоспособности очередного выходного параметра yj, j [1: m]. Так,

если y_j< T_j и коэффициент чувствительности положительный (т.е. sign(Bji) = 0) или y_j> T_j и sign(Bji) = 1, то

xi = xi_ном + Δ xi,

иначе

xi = xi_ном – Δ xi.

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

⇐ Предыдущая 30 31 32 33 343536 37 38 39 Следующая ⇒