9982

Численный анализ ИП в частотной области

Реферат

Информатика, кибернетика и программирование

Численный анализ ИП в частотной области. Как указывалось ранее при моделировании ИП в частотной области обычно используется численный спектральный подход. Наибольшие преимущества такой подход обеспечивает при моделировании линейных устройств. В связи с этим при вычи

Русский

2013-03-19

92.5 KB

1 чел.

Численный анализ ИП в частотной области.

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

Система линейных уравнений  в общем  случае  имеет  вид

АХ =В, или

где: X - вектор неизвестных переменных, В – вектор местных констант, А - квадратная матрица с элементами ( - номер строки, - номер   столбца).

Формально эту систему можно решить, обратив матрицу А:

Х= А-1В

Рисунок 1. Классификация методов решения системы линейных  уравнений

Решение систем линейных уравнений производится прямыми или итерационными методами (рис. 1).

Прямыми методами называют такие методы, которые позволяют за конечное число действий получить точное решение системы. Термин «точное решение» следует понимать условно как характеристику алгоритма, а не реального вычислительного процесса. Алгоритмы, лежащие в основе прямых метод дают точное решение, если все величины в системе заданы все вычисления проводятся абсолютно точно, без ошибок округления. К прямым методам относятся правило Крамера, методы Гаусса, Жордана и LU-разложения в различных модификациях.

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

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

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

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

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

Метод простой итерации

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

                 Ах= В                                             (1)

с квадратной невырожденной матрицей А, необходимо предварительно преобразовать эту систему к виду

                             х = Вх + с.                                             (2)

Здесь В — квадратная матрица с элементами bij (i, j = 1, 2, ..., m), с — вектор-столбец с элементами ci{ (г = 1, 2, ..., m).

В развернутой форме записи система (2) имеет следующий вид:

………………………………………………….……….

                                                                       (3)

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

Самый простой способ приведения системы к виду, удобному для итераций, состоит в следующем. Из первого уравнения системы (1) выразим неизвестное х1:

из второго уравнения - неизвестное х2-

и т д. В результате получим систему

......................................................................

                   (4)

в которой на главной диагонали матрицы  В находятся нулевые элементы. Остальные элементы выражаются по формулам

                                                                                (5)

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

Часто систему (1) преобразуют к виду х = х - r(Ах – b), где r - специально выбираемый числовой параметр.

2. Описание метода. Выберем начальное приближение x(0)=( x(0)1 x(0)2x(0)m)т. Подставляя его в правую часть системы (6.2) и вычисляя полученное выражение, находим первое приближение

х(1) = Bx(0) + с.

Подставляя приближение x(0) в правую часть системы (6.2), получим

х(2) = Bx(1) + с.

Продолжая этот процесс далее, получим последовательность х(0) х(1) …х(n)  

приближений, вычисляемых по формуле

                                                        (6)

В развернутой форме записи формула (6) выглядит так:

………………………………………….

                                               (7)

В случае, когда для итераций используется система (4) с коэффициентами, вычисленными по формулам (5), метод простой итерации принято называть методом Якоби.

Сходимость метода простой итерации.

Теорема. Пусть выполнено условие (8)

Тогда: 1) решение х системы (2) существует и единственно, 2) при произвольном начальном приближении x(0)   метод простой итерации сходится и справедлива оценка погрешности

Замечание 1. Теорема дает простое достаточное условие (8) сходимости метода простой итерации. Грубо это условие можно интерпретировать как условие достаточной малости элементов b матрицы В в системе, приведенной к виду (2).

Замечание   2. Если , то условие (8) принимает вид  

Для метода Якоби это условие в силу равенств bii = 0, bij = - aij /а* эквивалентно условию диагонального преобладания. Если же воспользоваться условием (8) при, то для метода Якоби получим другое условие диагонального преобладания:

                                                  (9)

4. Апостериорная оценка погрешности.

Предложение 6.1.  Если выполнено условие (8), то справедлива апостериорная оценка погрешности

                                                    (10)

Запишем равенство при k = п - 1 в виде

Тогда

Для завершения доказательства достаточно заметить, что полученное неравенство эквивалентно неравенству (10).

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

Если требуется найти решение с точностью e, то в силу (10) следует вести итерации до выполнения неравенства

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

                                              (11)

В практике вычислений иногда используют привлекательный своей простотой критерий окончания

                                                            (12)

Отметим, что для метода простой итерации его применение обосновано только тогда, когда  в этом случае  и выполнение неравенства (12) влечет за собой выполнение неравенства (11). Однако в большинстве реальных случаев величина оказывается близкой к единице и поэтому. В этих случаях e1< e и использование критерия (12) приводит к существенно преждевременному окончанию итераций. Величина здесь оказывается малой не потому, что приближения х(п-1) и х(п) близки к решению, а потому, что метод сходится медленно.

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

1. Описание метода. Пусть система (1) приведена к виду (4) с коэффициентами, вычисленными по формулам (5).

Метод Зейделя можно рассматривать как модификацию метода Якоби. Основная идея модификации состоит в том, что при вычислении очередного (k + 1)-го приближения к неизвестному xi при i > 1 используют уже найденные (k + 1)-е приближения к неизвестным, a не приближения, как методе Якоби.

На (k + 1)-й итерации компоненты приближения x(k+1) вычисляются по формулам

………………………………………….

                                                                         (13)

Введем нижнюю и верхнюю треугольные матрицы

,  

Тогда расчетные формулы метода примут компактный вид:

                                        (14)

Заметим, что В = В1 + В2 и поэтому решение х исходной системы удовлетворяет равенству

                                                 (15)

Метод Зейделя иногда называют также методом Гаусса-Зейделя, процессом Либмана, методом последовательных замещений.

2. Достаточные условия сходимости.

Теорема 6.3.    Пусть

где - одна из норм

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

3. Апостериорная оценка погрешности.

Предложение. Если выполнено условие  то для метода Зейделя справедлива апостериорная оценка погрешности

                                                      (16)

Положим k = п - 1 и запишем равенство (6.28) в следующем виде:

Тогда

откуда и следует неравенство (16).

Полученное неравенство позволяет сформулировать простой критерий окончания итерационного процесса. Если требуется найти решение с точностью e > 0, то итерации метода Зейделя следует вести до выполнения неравенства или эквивалентного ему неравенства

                             ,                                       (17)

Геометрическая интерпретация метода.

Приведем геометрическую интерпретацию метода Зейделя в случае m = 2, т.е. в случае решения системы

Первое уравнение задает на плоскости х1Ох2 прямую l1 второе - прямую l2 (рис. 2). Расчетные формулы метода принимают вид

где 

Рис. 2.

Пусть приближение х(k)  уже найдено. Тогда при определении х(k+1) координата х2= x2(k)  фиксируется и точка x перемещается параллельно оси  Ох1 до пересечения с прямой  l1. Координата х1 точки пересечения принимается за х1(k+1). Затем точка х перемещается вдоль прямой х1 = х1(k+1). до пересечения с прямой l2. Координата х2 Точки пересечения принимается за х1(k+1).

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


EMBED Equation.3


 

А также другие работы, которые могут Вас заинтересовать

4895. Банківські операції. Навчальний посібник 1.91 MB
  Передмова Ринкова економіка країни неможлива без існування банківської системи, банків і їх діяльності, яка б максимально задовольняла вимоги й очікування клієнтів і була б стійкою до криз. У сучасному ринковому середовищі підприємства через банківс...
4896. Техника безопасности при разработке месторождений полезных ископаемых открытым способом 413 KB
  Лекции по технике безопасности при разработке месторождений полезных ископаемых открытым способом Введение Основными нормативными документами по безопасности при проектировании и разработке месторождений твердых полезных ископаемых открытым способом...
4897. Аудит налогообложения. Сущность и назначение аудиторской деятельности 536 KB
  Тема 1. Сущность и назначение аудиторской деятельности 1.История развития аудита и его значение в рыночной экономике 2.Цель и задачи аудита 3.Принципы аудита 4.Виды аудита 1.История развития аудита и его значение в рыночной экономике Аудит - одна из...
4898. Основы маркетинга. Анализ рыночной ситуации в маркетинге. Конспект лекций 857.5 KB
  Введение в маркетинг План: Маркетинг и социально-экономическое развитие страны. Сущность и основные понятия маркетинга. Краткая история маркетинга и особенности его становления в России. Маркетинг как составная часть мене...
4899. Логістика. Навчально-методичний посібник 1.15 MB
  Метою вивчення дисципліни є формування системи знань з теорії, методології, методики та організаційних основ логістичного управління ресурсними потоками в національній економіці вивчення практики логістичного обслуговування споживачів різнома...
4900. Социологические исследования в библиотеках 968 KB
  В содержании и условиях деятельности российских библиотек происходят глубокие изменения. Библиотекам необходимо не только адаптироваться к новым экономическим, политическим, социокультурным условиям, но и выработать инновационные стратегии своего по...
4901. Управление персоналом: понятие и подходы 34.59 KB
  Управление персоналом: понятие и подходы Предприятие (организация, фирма), будучи целостной производственно-хозяйственной системой, тем не менее может быть представлено как совокупность составляющих ее элементов (подсистем), естественно взаимосвязан...
4902. Обзор моделей жизненного цикла разработки программного обеспечения 621 KB
  Обзор моделей жизненного цикла разработки программного обеспечения Модели жизненного цикла разработки ПО Определение модели ЖЦ разработки ПО Проект – это уникальный процесс, в ходе выполнения которого получают уникальный продукт. Таким об...
4903. CASE-технологии. Современные методы и средства проектирования информационных систем 1013.5 KB
  CASE-технологии. Современные методы и средства проектирования информационных систем Несмотря на высокие потенциальные возможности CASE-технологии (увеличение производительности труда, улучшение качества программных продуктов, поддержка унифицированн...