вторник, 16 ноября 2010 г.

Степенной метод на C++

Скууучно...Это пожалуй одна из самых простых лаб за чёрт знает сколько...Ну оно и к лучшему наверное - мне было бы лень расписывать здесь сейчас сложный-сложный алгоритм (:
Теория: 
  Дано: матрица 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 на внешние ссылки и т.п. :)

7 комментариев :

  1. у меня вопрос разве уместно здесь использовать
    memcpy() ведь он переносит байты... у меня к примеру в следствии работы твоего кода в векторе меняется только первое число остальные неизбежно заполняются единицами нулями двойками....
    не знаю с чем это связано...
    я поменял эту строчку на :
    for (int i=0; i<n; i++)Xn[i]=Xn1[i];
    на мой взгляд это более тривиально и работает точно без ошибок)))...

    ОтветитьУдалить
  2. Нуу...Наверное нет :) Вообще memcpy по идее быстрее for, но в нашем случае это какая-то жалкая лаба, а вектор X всего из двух-трёх элементов. Так что мало смысла на этом экономить. Но я фанат memcpy() и стараюсь его использовать вместо циклов там где это возможно в целях оптимизации (:...И даа...там ошибочка небольшая... sizeof(Xn)*_n - нужно просто sizeof(Xn). Хотя у меня и так работало и никаких сегментфолтов не было (:

    ОтветитьУдалить
  3. Не всё так просто, всё чуточку сложнее. Программа может упасть (даже скорее всего упадёт) с floating point exception на матрице fabs (i - j) размера скажем 50 на 50, точность 0.0000001. Это будет вызвано переполнением float. Для корректной работы каждую итерацию необходимо ещё проверять значение максимальной компоненты вектора, и если она превысила некоторое значение (1000, например) нормировать вектор. Нормировать можно даже в L_1, то есть без извлечения квадратного корня, как известно, все нормы в конечномерном пространстве эквивалентны.

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

    ОтветитьУдалить
  4. написал такую программу,но работает неправильно.В чем ошибка?


    #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();
    }

    ОтветитьУдалить
  5. В чем тут ошибка степенного метода?



    http://pastebin.com/1D8dXDCa

    ОтветитьУдалить
  6. Привет из 2021, принимаю эстафету по выч. методам

    ОтветитьУдалить