Задача 8. Собственное число

Найти наибольшее собственное число заданной квадратной матрицы.

{ Решение задачи 8 на языке PASCAL }

CONST N=3;

TYPE TVector=ARRAY[1..N] OF Real;

TMatrix=ARRAY[1..N] OF TVector;

CONST a : TMatrix = ((11,-6,2),(-6,10,-4),(2,-4,6));

x : TVector = (1,1,1);

Error = 1E-10;

Limit = 100;

VAR Iteration : Word;

L,L0,s : Real;

i,j : Byte;

y : TVector;

BEGIN Iteration:=0; L:=0;

REPEAT

Inc(Iteration); L0:=L; L:=0;

FOR i:= 1 TO N DO BEGIN

s:=0;

FOR j:=1 TO N DO s:=s+a[i,j]*x[j];

IF Abs(s)>Abs(L) THEN L:=s; y[i]:=s;

END;

FOR i:=1 TO N DO x[i]:=y[i]/L;

UNTIL (Iteration=Limit)OR(Abs(1-L0/L)<Error);

WriteLn('Наибольшее собственное значение матрицы=',L,#10,#13,

'Достигнута относительная погрешность ',Abs(1-L0/L):7,

' за ',Iteration:3,' итераций',#10,#13,

'Соответствующий собственный вектор :');

FOR i:=1 TO N DO WriteLn(' x[',i:2,']=',x[i]);

END.

// Решение задачи 8 на языке C

#include<stdio.h>

#include<math.h>

#define N 3

void main(void){

double a[][N]={11,-6,2,-6,10,-4,2,-4,6}, x[]={1,1,1},

Error=1E-10,L=0,L0,s,y[N];

int Limit=100,Iteration=0,i,j;

do{

for(L0=L,L=0,i=0;i<N;i++)

for(s=0,j=0;j<N;j++){s+=a[i][j]*x[j];if(fabs(s)>fabs(L))L=s;y[i]=s;}

for(i=0;i<N;i++)x[i]=y[i]/L;}

while(++Iteration<Limit&&fabs(1-L0/L)>=Error);

printf("\nНаибольшее собственное значение матрицы=%g\n"

"Достигнута относительная погрешность %g за %d итераций\n"

"Соответствующий собственный вектор :\n",L,fabs(1-L0/L),Iteration);

for(i=0;i<N;i++)printf("\tx[%2d]=%g\n",i+1,x[i]);}

C Решение задачи 8 на языке FORTRAN

PARAMETER(N=3)

REAL*8 a(N,N)/11,-6,2,-6,10,-4,2,-4,6/,x(N)/1,1,1/,Error/1E-10/,

& L/0/,L0,s,y(N)

INTEGER Limit/100/

Iteration=0

1 Iteration=Iteration+1

L0=L

L=0

DO 2 i=1,N

s=0

DO 3 j=1,N

3 s=s+a(i,j)*x(j)

IF(ABS(s).GT.ABS(L))L=s

2 y(i)=s

x=y/L

IF(Iteration.LT.Limit.AND.ABS(1-L0/L).GE.Error)GOTO 1

PRINT 998,L,ABS(1-L0/L),Iteration

998 0FORMAT(' Наибольшее собственное значение матрицы='G8.2/

1 ' Достигнута относительная погрешность 'G7.1' за 'I3

2 ' итераций'/' Соответствующий собственный вектор :')

PRINT 999,(i,x(i),i=1,N)

999 FORMAT(' x['I2']='G10.2)

END

Комментарии к задачам

Задача 1. Вывод натурального числа

Вывод числа в десятичном виде очевиден. При выводе числа в двоичном виде используются битовые операции AND,ShL,ShR (Pascal), &,<<,>> (C), или битовые функции IAND,ISHL (FORTRAN). Очевидно, что число содержит не более 20 значащих двоичных цифр. Восьмеричное представление числа получено в Pascal-программе и Fortran-программе точно так же, а в языке C есть специальный восьмеричный формат. Шестнадцатеричное представление числа получено в C-программе и FORTRAN-про­грамме средствами формата, а на языке Pascal для этого пришлось записать специальный алгоритм.

Задача 2. Сумма ряда

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

Задача 3. Медленная сортировка

Алгоритм сортировки очевиден. Программы иллюстрируют обработку одномерных массивов.

Задача 4. Быстрая сортировка

Алгоритм сортировки бинарными вставками состоит в следующем: первый элемент массива есть упорядоченный массив длиной 1. Возьмем первый элемент неупорядоченного массива (второй элемент исходного массива) и вставим его в упорядоченный массив, не нарушая упорядоченности. Получим упорядоченный массив длиной 2 и неупорядоченный массив длиной n-2. Будем повторять эту операцию до тех пор, пока длина неупорядоченного массива не станет равной нулю. Место вставки нового элемента в упорядоченный массив ищется методом бисекции, это позволяет понизить сложность всего алгоритма до nln(n). Программы иллюстрируют использование подпрограмм и встроенного генератора случайных чисел.

Задача 5. Слова

Программы иллюстрируют способы обработки текстовых файлов и работу с символьными строками. В этих программах заметны отличия в представлении символьных данных в языках Pascal, C и Fortran. В Fortran-программе пришлось записать функцию Length для вычисления фактической длины строки, так ка язык не предоставляет таких средств. Обратите внимание, что остаток строки может быть заполнен пробелами или нуль-символами. Pascal-программа очень продуктивно использует возможность описания массива с символьными индексами и переменные типа “множе­ство”.

Задача 6. График

Pascal-программа и C-программа практически идентичны, так как используют один и тот же графический интерфейс, графические средства языка Fortran существенно отличаются. В C-программе использовано макроопределение F(x), а в Fortran-программе - оператор-функция F(x). Все три программы предполагают, что в текущем каталоге есть все необходимые файлы поддержки (графический драйвер для Pascal-программы и C-про­граммы и шрифтовые файлы для всех трех программ).

Задача 7. Кубическое уравнение

Программы реализуют решение Кардано кубического уравнения с вещественными коэффициентами (см.: Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. М.: Наука, 1970. С.43). В виде исключения приведено четыре решения - на языках Pascal, C, Fortran и C++. Языки Fortran и C++ поддерживают комплексный тип данных, поэтому алгоритм записывается в этих двух программах просто и естественно. В Pascal-программе и C-программе пришлось моделировать комплексные числа записями (структурами) и написать несколько функций для обработки таких данных.

Задача 8. Собственное число

Использованный в программах итерационный метод вычисления наибольшего собственного числа L и соответствующего собственного вектора X квадратной матрицы А заключается в следующем : задается некоторый достаточно произвольный вектор X⁰. Вычисляется вектор AX⁰ и его норма (максимум из абсолютных величин компонентов), которая дает первое приближение L¹ для собственного числа, а первое приближение для собственного вектора X¹ получается нормировкой вектора AX⁰. Вторая и все остальные итерации выполняются аналогично. Итерационный процесс заканчивается, когда либо относительная погрешность собственного числа станет меньше заданной предельно допустимой ошибки, либо количество итераций достигнет заданного предельного значения.

91