Скууучно...Это пожалуй одна из самых простых лаб за чёрт знает сколько...Ну оно и к лучшему наверное - мне было бы лень расписывать здесь сейчас сложный-сложный алгоритм (:
Теория:
Дано: матрица A размера (NxN)
Найти требуется максимальное собственное число матрицы.
Алгоритм:
1) Выбираем вектор X0 - начальное приближение, при этом X0!=0;
2) Строим Xn+1=A*Xn=An+1 * X0
3) Находим λn=(Xn+1, Xn)/(Xn, Xn); (Где запятая - скалярное умножение векторов)
Критерий окончания: |λn-λn-1|<E
Практика
Для начала разберёмся с двумя функциями, которые впоследствии будем использовать:
Умножение матрицы на вектор:
void matrix_m_vector(float **m, float *v, float *res)
{
for (int i=0; i<_n; i++)
{
res[i] = 0;
for (int j=0; j<_n; j++){
res[i]+=m[i][j]*v[j];
}
}
}
Скалярное умножение векторов:
void vector_m_vector(float *v1, float *v2, float *res)
{
for (int i=0; i<_n; i++)
{
*res+=v1[i]*v2[i];
}
}
Правильнее было бы написать красивые классы для матрицы и вектора, перегрузить в них опрерации умножения, всё по фен-шую...Но данная лаба делается за 20 минут и сдаётся за минуту, а потом успешно забрасывается в угол. Какой в этом, спрашивается, смысл?
Перменная A содержит собственно нашу исходную матрицу размера NxN, Xn, соответственно вектор, на первой итерации равный X0; т.е. начальному приближению, переменная L будет использоваться для хранения лямбды.
Вот непосредственно сама реализация всего алгоритма в одном маленьком цикле:
while(1)
{
matrix_m_vector(A, Xn, Xn1);
float num=0,den=0;
vector_m_vector(Xn1, Xn, &num);
vector_m_vector(Xn, Xn, &den);
float Lprev=L;
L=num/den;
if ((fabs(L-Lprev))<0.00001) break;
memcpy(Xn, Xn1, sizeof(Xn)*_n);
it++;
}
cout << "λmax= "<<setprecision(6) << L <<endl;
cout << "Итераций: " << it;
Ну собственно вот и всё! (: Надеюсь данный материал будет полезен тем, кто либо лекции потерял, либо вовсе на них не был.
P.S. В тайтле написано C++. На самом деле здесь только pure Си. Просто как правило люди гуглят C++. Надо же как-то с гуглботом дружиться помимо запрета индексации архива, ярлыков, noindex на внешние ссылки и т.п. :)
у меня вопрос разве уместно здесь использовать
ОтветитьУдалитьmemcpy() ведь он переносит байты... у меня к примеру в следствии работы твоего кода в векторе меняется только первое число остальные неизбежно заполняются единицами нулями двойками....
не знаю с чем это связано...
я поменял эту строчку на :
for (int i=0; i<n; i++)Xn[i]=Xn1[i];
на мой взгляд это более тривиально и работает точно без ошибок)))...
Нуу...Наверное нет :) Вообще memcpy по идее быстрее for, но в нашем случае это какая-то жалкая лаба, а вектор X всего из двух-трёх элементов. Так что мало смысла на этом экономить. Но я фанат memcpy() и стараюсь его использовать вместо циклов там где это возможно в целях оптимизации (:...И даа...там ошибочка небольшая... sizeof(Xn)*_n - нужно просто sizeof(Xn). Хотя у меня и так работало и никаких сегментфолтов не было (:
ОтветитьУдалитьНе всё так просто, всё чуточку сложнее. Программа может упасть (даже скорее всего упадёт) с floating point exception на матрице fabs (i - j) размера скажем 50 на 50, точность 0.0000001. Это будет вызвано переполнением float. Для корректной работы каждую итерацию необходимо ещё проверять значение максимальной компоненты вектора, и если она превысила некоторое значение (1000, например) нормировать вектор. Нормировать можно даже в L_1, то есть без извлечения квадратного корня, как известно, все нормы в конечномерном пространстве эквивалентны.
ОтветитьУдалитьПрограмма всё равно даже после этого может падать при больших числах в исходной матрице, но эта проблема так же решается выбором начального вектора так, чтобы его норма не превосходила 1.
написал такую программу,но работает неправильно.В чем ошибка?
ОтветитьУдалить#include
#include
#include
#include
#include
#define n 3
float L,E;
int i,j,it;
void matrix_m_vector(float **m, float *v, float *res)
{
for ( i=0; i>A[i][j];
}
}
for( i=0;i>Xn[i];
cout<<"\nE=";
cin>>E;
while(1)
{
matrix_m_vector(A, Xn, Xn1);
float num=0,den=0;
vector_m_vector(Xn1, Xn, &num);
vector_m_vector(Xn, Xn, &den);
float Lprev=L;
L=num/den;
if ((fabs(L-Lprev))<E) break;
memcpy(Xn, Xn1, sizeof(Xn));
it++;
}
cout << "max= "<<setprecision(6) << L <<endl;
cout << "Iterations: " << it;
getch();
}
В чем тут ошибка степенного метода?
ОтветитьУдалитьhttp://pastebin.com/1D8dXDCa
Привет из 2021, принимаю эстафету по выч. методам
ОтветитьУдалитьчто такое setprecision(6)?
ОтветитьУдалить