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


 

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

9002. Философия и мировоззрение. Специфика философии 39 KB
  Философия и мировоззрение. Специфика философии Философия - учение о мире в целом, об общих принципах и закономерностях его бытия и познания. Органическое соединение в философии двух начал - научно-теоретического и практически-духовного...
9003. Предмет, структура и функции философии, всеобщие свойства и связи 43.5 KB
  Предмет, структура и функции философии Предметом философии являются всеобщие свойства и связи (отношения) действительности - природы, общества, человека, отношения объективной действительности и субъективного мира, материального и идеального, б...
9004. Философия Древнего Востока. Проблема совершенного человека 38.5 KB
  Философия Древнего Востока. Проблема совершенного человека Буддизм - религиозно-философское учение, возникшее в древней Индии в VI – V вв. до н. э. и превратившееся в ходе его развития в одну из трех - наряду с христианством и исламом...
9005. Ранняя греческая философия. Древнегреческая философия 40.5 KB
  Ранняя греческая философия Древнегреческая философия представляет собой совокупность учений, развившихся с VI в. до н.э. по VI в. н.э. (от формирования архаических полисов на ионийском и италийском побережьях до расцвета демократических Афин и после...
9006. Философия Платона. Теория идей, познание, человек и государство у Платона 42.5 KB
  Философия Платона. Теория идей, познание, человек и государство у Платона После казни Сократа один из его лучших учеников Аристокл, получивший за свои широкие плечи прозвище Платон («широкоплечий»), надолго покинул Афины. Тяжело переживая смерть учи...
9007. Философия Аристотеля. Бытие, сущность, причинность, душа, материя и форма 44 KB
  Философия Аристотеля. Бытие, сущность, причинность, душа, материя и форма Аристотель (384 – 322 гг. до н. э.) - древнегреческий философ, энциклопедист, основоположник науки логики и ряда отраслей специального знания. Образование Аристотель...
9008. Античные школы стоиков, скептиков и эпикурейцев 28.5 KB
  Античные школы стоиков, скептиков и эпикурейцев Философия в период эллинизма частично изменила содержание и свои основные цели. Эти изменения были обусловлены социально-экономическими и политическими процессами в развивавшемся эллинистическом общест...
9009. Идеи рационализма в учениях Р. Декарта, Б. Спинозы и Г. В. Лейбница 50 KB
  Идеи рационализма в учениях Р. Декарта, Б. Спинозы и Г. В. Лейбница Идеи мыслителей эпохи Возрождения были развиты философией Нового времени. Прогресс опытного знания, науки требовал замены схоластического метода мышления новым методом познания, обр...
9010. Периоды, представители и проблемы философии Средневековья и Возрождения 44 KB
  Периоды, представители и проблемы философии Средневековья и Возрождения Средневековая европейская философия - важный этап в истории философии, связанный прежде всего с христианством. Хронологически этот период охватывает V –XV вв. Специфик...