ریاضیات :: دکتر زینگ

متوسط:

برای تقریب جواب معادلات ریاضی توسط کامپیوتر (با هر اندازه دقت) می توانیم از سه روش استفاده کنیم که به طور اختصار و کاربردی دو روش را در این پست و روش سوم که روش نیوتن است در پستی جداگانه بررسی می کنیم.

نکته ای که باید قبل از بررسی روش ها توجه کنید این است که معادله را باید بتوان به صورت f(x) =0 تبدیل کرد که ما در مثال های که در ادامه ذکر می کنیم تابع معادله به صورت ( double f(double x تعریف شده است. نکته ی دیگر اینکه بازه ای که معادله دارای جواب است را بدانیم که ما به طور پیش فرض بازه ی جواب معادله را بین ۰ و ۱ در نظر گرفته ایم.

Bisection method :

این روش با روش جست و جوی دودویی مشابهت زیادی دارد. با این تفاوت که ما در بررسی پیشروی بازه ی جواب به جای بررسی تفاوت( کوچکی و بزرگی‌) به بررسی تغییر علامت های دو نقطه ی بالایی و پایینی می پردازیم.

کد سی این برنامه به این صورت است:

if(f(0) * f(1) > 0)
printf( "No solution\n" );

else {

for( u = 0 , v = 1 ; v - u >= Precision ; ) // be jaye Precision mizan deghat gharar migirad masalan 0.0001

{ c = (v + u)/2;
if( f( c ) * f(u) > 0) u = c;

         else                           v = c;
   }
        printf("%0.4lf\n" , u );
}

Secant method :

این روش نیز مانند روش قبلی با دو نقطه به عنوان ابتدا و انتهای محدوده ی جواب آغاز می شود. این روش بدین صورت است که در هر مرحله نقطه ی جدیدی بوجود می آید و ادامه ی کار با این نقطه و نقطه ی بوجود آمده ی قبل از آن از سر گرفته می شود. طریقه ی بوجود آمدن هر نقطه بدین صورت است که خطی که از دو نقطه ی آخر عبور می کند را با خط افقی محور تلاقی می دهیم. نقطه ی تلاقی این خط با محور نقطه ی جدید است. به عبارت دیگر اگر به ترتیب نقطه های X0 و X1 را داشته باشیم نقطه ی X2 به این صورت بوجود می آید :

$y=\frac{f(x_1)-f(x_0)}{x_1-x_0}(x-x_1) + f(x_1)$

$x_2=x_1-f(x_1)\frac{x_1-x_0}{f(x_1)-f(x_0)}$

معادله خط گذرنده از دو نقطه :

اگر y = 0 آنگاه X2 برابر است با :

یکی از روش های پیاده سازی Secant بدین شکل می باشد :

if(f(0) * f(1) > 0)
printf( "No solution\n" );

else {

for( u = 0 , v = 1 ; ; )

   {
            fu = f(u);
            fv = f(v);
            if( fabs(fv -fu) < Precision ) // be jaye Precision mizan deghat gharar migirad
                break;
            c = v - fv * ( v - u ) / (fv - fu) ;
            swap( u , v );   u = c;
   }

printf("%0.4lf\n" , u );

}

روش دیگر پیاده سازی :

if(f(0) * f(1) > 0)
printf( "No solution\n" );

else {

for( u = 0 , v = 1 ; ; )

   {
            fu = f(u);
            fv = f(v);
d = f(v)*(v-u)/(f(v)-f(u)); if (fabs(d) < EPS) break; u = v; v = v - d;    }

printf("%0.4lf\n" , v );

}

مقدماتی:

یکسری مفاهیم ابتدایی از دنباله ی فیبوناچی:

f(0) = 0 ; f(1) = 1 ; f(n > 2) = f(n-1) + f(n-2);
Digits:
1. f(50) : 10 digits
2. f(100): 20 digits
3. f(500): 105 digits
4. f(1000): 210 digits
5. f(4800): 1000 digits
Negative fibo:

$F_{-n} = (-1)^{n+1} F_n. \,$

F₋₈

F₋₇

F₋₆

F₋₅

F₋₄

F₋₃

F₋₂

F₋₁

F₀

F₁

F₂

F₃

F₄

F₅

F₆

F₇

F₈

−21

13

−8

5

−3

2

−1

1

0

1

1

2

3

5

8

13

21

F₋₈	F₋₇	F₋₆	F₋₅	F₋₄	F₋₃	F₋₂	F₋₁	F₀	F₁	F₂	F₃	F₄	F₅	F₆	F₇	F₈
−21	13	−8	5	−3	2	−1	1	0	1	1	2	3	5	8	13	21

کد زیر با اردر n سری فیبوناچی از ۱ تا n را بدست می آورد اما نکته ای که باید اینجا به آن دقت کرد این است که سرعت رشد تعداد ارقام در فیبوناچی بسیار زیاد است. بدین صورت که اگر آرایه fibo از نوع int باشد n <= 45 و اگر long long باشد n<=92 پس برای n>92 باید از روش دیگری استفاده کرد که در ادامه به بررسی آن می پردازیم.

fibo[0] = 0; fibo[1] = 1;

for( int i = 0 ; i < n ; i++ ) // n baraye int ۴۵ ba baraye long long kamtar az ۹۲ mibashad

fibo[i] = fibo[i-1] + fibo[i-2];

البته فرمولی با اردر ۱ وجود دارد که به شرح زیر است:

$F_n = \frac{\varphi^n-\psi^n}{\varphi-\psi} = \frac{\varphi^n-\psi^n}{\sqrt 5}$ $\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.61803\,39887\dots\,$

$\psi = \frac{1 - \sqrt{5}}{2} = 1 - \varphi = - {1 \over \varphi}.$

اما به دلیل توان n که در این فرمول وجود دارد

استفاده از این فرمول توصیه نمی شود.

متوسط:

برای محاسبه ی دنباله ی فیبوناچی ارقام بزرگتر از ۹۲ باید از آرایه ی ۲ بعدی استفاده کرد بدین صورت که درایه ی اول برای شماره ی فیبوناچی و درایه دوم برای رقم های فیبوناچی اختصاص پیدا می کند. {fibo[n][k برابر است با رقم k از سمت راست برای(F(n.

طریقه ی محاسبه:

    fibo[0][0] = 0;    num[0] = 0;
    fibo[1][0] = 1;    num[1] = 0;
    for( int i = 2 ; i < 5000 ;i ++ )
    {
        for( int j = 0 ; j < 10005; j++ )
            fibo[i][j] = fibo[i-1][j] + fibo[i-2][j];
        for( int j = 0 ; j < 10005; j++ )
        {
            if(fibo[i][j] >= 10 )
            {
                fibo[i][j+1] += fibo[i][j] / 10;
                fibo[i][j] %= 10;
            }
            if( fibo[i][j] != 0 )        num[i] = j;
        }
    }

محتوای آرایه num درایه آخرین خانه ی پر شده یا به عبارت دیگر آدرس آخرین رقم دنباله است.
در هنگام استفاده از متغیر fibo باید به این نکته توجه کرد که [fibo[i][0 رقم یکان و
[ [fibo[i][ num[n آخرین رفم دنباله می باشد.

دکتر زینگ

الگوریـــتـم

۲ مطلب با کلمه‌ی کلیدی «ریاضیات» ثبت شده است

حل معادلات ریاضی (۱)

فیبوناچی ۱

الگوریتم زندگی همانچیزی که نظم طبیعت بر آن دقیق شده است.

الگوریتم

هوش مصنوعی

انگیزشی

ایده