algorithm
Ekvationslösning
Sök…
Linjär ekvation
Det finns två klasser av metoder för att lösa linjära ekvationer:
Direktmetoder : Vanliga egenskaper hos direkta metoder är att de omvandlar den ursprungliga ekvationen till ekvivalenta ekvationer som lättare kan lösas, vilket innebär att vi löser direkt från en ekvation.
Iterativ metod : Iterativa eller indirekta metoder, börja med en gissning av lösningen och förfina sedan upprepade gånger lösningen tills ett visst konvergenskriterium har uppnåtts. Iterativa metoder är i allmänhet mindre effektiva än direkta metoder eftersom ett stort antal operationer krävs. Exempel - Jacobis Iteration Method, Gauss-Seidal Iteration Method.
Implementering i C-
//Implementation of Jacobi's Method
void JacobisMethod(int n, double x[n], double b[n], double a[n][n]){
double Nx[n]; //modified form of variables
int rootFound=0; //flag
int i, j;
while(!rootFound){
for(i=0; i<n; i++){ //calculation
Nx[i]=b[i];
for(j=0; j<n; j++){
if(i!=j) Nx[i] = Nx[i]-a[i][j]*x[j];
}
Nx[i] = Nx[i] / a[i][i];
}
rootFound=1; //verification
for(i=0; i<n; i++){
if(!( (Nx[i]-x[i])/x[i] > -0.000001 && (Nx[i]-x[i])/x[i] < 0.000001 )){
rootFound=0;
break;
}
}
for(i=0; i<n; i++){ //evaluation
x[i]=Nx[i];
}
}
return ;
}
//Implementation of Gauss-Seidal Method
void GaussSeidalMethod(int n, double x[n], double b[n], double a[n][n]){
double Nx[n]; //modified form of variables
int rootFound=0; //flag
int i, j;
for(i=0; i<n; i++){ //initialization
Nx[i]=x[i];
}
while(!rootFound){
for(i=0; i<n; i++){ //calculation
Nx[i]=b[i];
for(j=0; j<n; j++){
if(i!=j) Nx[i] = Nx[i]-a[i][j]*Nx[j];
}
Nx[i] = Nx[i] / a[i][i];
}
rootFound=1; //verification
for(i=0; i<n; i++){
if(!( (Nx[i]-x[i])/x[i] > -0.000001 && (Nx[i]-x[i])/x[i] < 0.000001 )){
rootFound=0;
break;
}
}
for(i=0; i<n; i++){ //evaluation
x[i]=Nx[i];
}
}
return ;
}
//Print array with comma separation
void print(int n, double x[n]){
int i;
for(i=0; i<n; i++){
printf("%lf, ", x[i]);
}
printf("\n\n");
return ;
}
int main(){
//equation initialization
int n=3; //number of variables
double x[n]; //variables
double b[n], //constants
a[n][n]; //arguments
//assign values
a[0][0]=8; a[0][1]=2; a[0][2]=-2; b[0]=8; //8x₁+2x₂-2x₃+8=0
a[1][0]=1; a[1][1]=-8; a[1][2]=3; b[1]=-4; //x₁-8x₂+3x₃-4=0
a[2][0]=2; a[2][1]=1; a[2][2]=9; b[2]=12; //2x₁+x₂+9x₃+12=0
int i;
for(i=0; i<n; i++){ //initialization
x[i]=0;
}
JacobisMethod(n, x, b, a);
print(n, x);
for(i=0; i<n; i++){ //initialization
x[i]=0;
}
GaussSeidalMethod(n, x, b, a);
print(n, x);
return 0;
}
Icke-linjär ekvation
En ekvation av typen f(x)=0 är antingen algebraisk eller transcendental. Dessa typer av ekvationer kan lösas med hjälp av två typer av metoder-
Direkt metod : Den här metoden ger det exakta värdet för alla rötter direkt i ett begränsat antal steg.
Indirekt eller itterativ metod : Iterativa metoder passar bäst för datorprogram för att lösa en ekvation. Det bygger på begreppet successiv tillnärmning. I Iterative Method finns det två sätt att lösa en ekvation-
Bracketing-metod : Vi tar två initiala punkter där roten ligger mellan dem. Exempel - Halvmetod, falsk positionsmetod.
Open End Method : Vi tar ett eller två initialvärden där roten kan vara var som helst. Exempel - Newton-Raphson-metod, successiv tillnärmningsmetod, säker metod.
Implementering i C-
/// Here define different functions to work with
#define f(x) ( ((x)*(x)*(x)) - (x) - 2 )
#define f2(x) ( (3*(x)*(x)) - 1 )
#define g(x) ( cbrt( (x) + 2 ) )
/**
* Takes two initial values and shortens the distance by both side.
**/
double BisectionMethod(){
double root=0;
double a=1, b=2;
double c=0;
int loopCounter=0;
if(f(a)*f(b) < 0){
while(1){
loopCounter++;
c=(a+b)/2;
if(f(c)<0.00001 && f(c)>-0.00001){
root=c;
break;
}
if((f(a))*(f(c)) < 0){
b=c;
}else{
a=c;
}
}
}
printf("It took %d loops.\n", loopCounter);
return root;
}
/**
* Takes two initial values and shortens the distance by single side.
**/
double FalsePosition(){
double root=0;
double a=1, b=2;
double c=0;
int loopCounter=0;
if(f(a)*f(b) < 0){
while(1){
loopCounter++;
c=(a*f(b) - b*f(a)) / (f(b) - f(a));
/*/printf("%lf\t %lf \n", c, f(c));/**////test
if(f(c)<0.00001 && f(c)>-0.00001){
root=c;
break;
}
if((f(a))*(f(c)) < 0){
b=c;
}else{
a=c;
}
}
}
printf("It took %d loops.\n", loopCounter);
return root;
}
/**
* Uses one initial value and gradually takes that value near to the real one.
**/
double NewtonRaphson(){
double root=0;
double x1=1;
double x2=0;
int loopCounter=0;
while(1){
loopCounter++;
x2 = x1 - (f(x1)/f2(x1));
/*/printf("%lf \t %lf \n", x2, f(x2));/**////test
if(f(x2)<0.00001 && f(x2)>-0.00001){
root=x2;
break;
}
x1=x2;
}
printf("It took %d loops.\n", loopCounter);
return root;
}
/**
* Uses one initial value and gradually takes that value near to the real one.
**/
double FixedPoint(){
double root=0;
double x=1;
int loopCounter=0;
while(1){
loopCounter++;
if( (x-g(x)) <0.00001 && (x-g(x)) >-0.00001){
root = x;
break;
}
/*/printf("%lf \t %lf \n", g(x), x-(g(x)));/**////test
x=g(x);
}
printf("It took %d loops.\n", loopCounter);
return root;
}
/**
* uses two initial values & both value approaches to the root.
**/
double Secant(){
double root=0;
double x0=1;
double x1=2;
double x2=0;
int loopCounter=0;
while(1){
loopCounter++;
/*/printf("%lf \t %lf \t %lf \n", x0, x1, f(x1));/**////test
if(f(x1)<0.00001 && f(x1)>-0.00001){
root=x1;
break;
}
x2 = ((x0*f(x1))-(x1*f(x0))) / (f(x1)-f(x0));
x0=x1;
x1=x2;
}
printf("It took %d loops.\n", loopCounter);
return root;
}
int main(){
double root;
root = BisectionMethod();
printf("Using Bisection Method the root is: %lf \n\n", root);
root = FalsePosition();
printf("Using False Position Method the root is: %lf \n\n", root);
root = NewtonRaphson();
printf("Using Newton-Raphson Method the root is: %lf \n\n", root);
root = FixedPoint();
printf("Using Fixed Point Method the root is: %lf \n\n", root);
root = Secant();
printf("Using Secant Method the root is: %lf \n\n", root);
return 0;
}