Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Методичка по методам оптимизации.doc
Скачиваний:
179
Добавлен:
02.05.2014
Размер:
1.18 Mб
Скачать

Элементарные преобразования матриц. Метод гаусса

Постановка задачи.

Решить систему линейных алгебраических уравнений

a11x1 + . . . + a1n xn = a10

. . . . . . . . . . . . . . . . . . . . . . (1.1)

am1x1 + . . . + amnxn = am0

что означает:

  1. определить, совместимая данная система ли (то есть, имеет ли она хотя бы одно решение);

  2. если система совместимая, то, имеет ли она единственное решение, или таких решений множество;

  3. найти решение, если он единственный, и найти общее решение в случае существования множества решений.

Вопрос совместимости системы (1.1) решает теорема Кронекера-Капелли, формулировка которой такая:

Система линейных алгебраических уравнений (1.1) совместимая в том и только в том случае, когда совпадают ранги основной и расширенной матриц

a11

. . .

a1n

a11

. . .

a1n

a10

А =

. . .

. . .

. . .

,

A=

. . .

. . .

. . .

. . .

.

am1

. . .

amn

am1

. . .

amn

am0

При этом решение единственное тогда и только затем, когда rang(A)=n. Если же rang(A)=r<n, то обязательно найдутся такие r переменных , что исходная система (1.1) будет эквивалентной системе вида:

(1.2)

где суммирование ведется по j=1...,n, отличных от i1...,ir.

О системе (1.2) говорят, что она решена относительно переменных и имеет каноничный вид.

Общее решение системы (1.2) определяется тривиально:

(1.3)

В уравнениях (1.3) переменные xj (j отличное от i1...,ir) — свободные переменные, они могут получать произвольные значения. Каждая совокупность их значений однозначно определяет значение переменных — базисных переменных.

Метод Гаусса является основным законченным методом решить систем линейных алгебраических уравнений (1.1) и заключается в исполнении однотипных превращений исключения.

На 1-м шаге метода находят переменную в 1-м уравнении, коэффициент возле которой не равняется нулю, и исключают эту переменную из всех других уравнений. Если, например, a11 не равняется нулю, то превращения 1-го шага такие: до і-го уравнения прибавить 1-е уравнение, умноженное на число –ai1a11, i=2...,m.

В результате превращений 1-го шага система (1.1) приобретает вид:

a11x1 + a12x2 + . . . + a1n xn = a10

а22х2 + . . . + а2nxn = а20

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . (1.4)

аm2x2 + . . . + аmnxn = аm0.

На следующем шаге эта же последовательность действий применяется к части системы, что состоит из системы (1.4) без 1-го уравнения и т.д. Упомянутый процесс продолжается до тех пор, пока не будет получена система трапециевидного (в частности, треугольного) вида, или не будет подтвержден признак несовместимости системы.

Описанные превращения составляют прямой ход метода Гаусcа. При прямом ходу превращения выполняются «сверху вниз» — от первого уравнения к последнему. Обратный ход метода Гаусса составляют превращения исключения отделенных при прямом ходу базисных переменных, при этом превращения выполняются в обратном порядке: от последнего уравнения к первому — «снизу вверх».

Прямой и обратный ход метода Гаусса достал название метода полного исключения Жордана-Гаусса.

Кроме основного назначения (как метода решить систем линейных алгебраических уравнений) метод Гаусcа имеет и другие важные применения.

С помощью прямого хода метода Гаусcа можно вычислять численные определители (путем сводки определителя к треугольному виду).

Метод Жордана-Гаусcа позволяет находить обратные матрицы.

Пусть имеем некоторую невырожденную квадратную матрицу:

a11

. . .

a1n

A=

. . .

. . .

. . .

.

an1

. . .

ann

Построим расширенную матрицу вида:

a11

. . .

a1n

1

. . .

0

. . .

. . .

. . .

. . .

. . .

. . .

an1

. . .

ann

0

. . .

1

и применим к ней метод Жордана-Гауcса. Если в результате получим матрицу вида:

1

. . .

0

b11

. . .

b1n

. . .

. . .

. . .

. . .

. . .

. . .

,

0

. . .

1

bn1

. . .

bnn

то

b11

. . .

b1n

. . .

. . .

. . .

bn1

. . .

bnn

обратная матрица к исходной матрице А.

Программное обеспечение.

Модуль, который выполняет элементарные превращения матриц, которые лежат в основе метода Гауcса, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПОМО.

Задание.

методом Гауcса системы линейных алгебраических уравнений, расширенные матрицы которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9), а также следующие задачи.

методом Гаусса системы линейных алгебраических уравнений, что заданы расширенными матрицами:

1)

2

-2

0

1

-3

2)

1

1

-6

-4

6

3)

2

-1

3

4

5

2

3

1

-3

-6

3

-1

-6

-4

2

4

-2

5

6

7

3

4

-1

2

0

2

3

9

2

6

6

-3

7

8

9

1

3

1

-1

2

3

2

3

8

-7

8

-4

9

10

11

Вычислить следующие определители:

4)

0

1

1

1

5)

1

1

6

4

6)

3

6

5

6

4

1

0

1

1

3

1

6

4

5

9

7

8

6

1

1

0

1

2

3

9

2

6

12

13

9

7

1

1

1

0

3

2

3

8

2

5

4

5

3

4

6

6

5

4

Найти обратные к таким матрицам:

7)

1

1

1

1

8)

1

2

3

4

9)

3

6

5

6

1

1

-1

-1

2

3

1

2

5

9

7

8

1

-1

1

-1

1

1

1

1

6

12

13

9

1

-1

-1

1

1

0

2

6

2

5

4

5

Лабораторная работа 2.