Polynomial Optimization and Root Finding
Budget: $30 – $250 USD
The project consists of two phases. In the first phase, you are required to write a program that can calculate all the roots, including the complex ones, of a polynomial Pn(x) of positive integer degree n and the coefficient a0 of xn is positive. The solution method is recursive, which means it will break down the problem into smaller sub-problems until it can solve them easily.
The recursive solution method has the following steps:
Step 1: If the degree of the polynomial Pn(x) is less than or equal to 4, use the solve_p4c.c program to find the roots.
Step 2: If the degree of the polynomial Pn(x) is even, find a segment (a,b) where Pn(a)Pn(b) < 0. You can calculate Pn(0) to determine which value to use for a and b. Then use the bisection method or the bisection method with regula falsi to find a real root x. After finding x*, do a long division of Pn(x) by (x-x*) and recursively call the algorithm on Qn-1(x).
Step 3: If the degree of the polynomial Pn(x) is odd, use Newton's complex method to find a root x* which may be complex x*=a*+bi. If x turns out to be real (b in absolute value is less than epsilon), do a long division of Pn(x) by (x-a*) and recursively call the algorithm on Qn-1(x). If x* turns out to be complex, do a long division of Pn(x) by (x2-2ax2+(a)2+(b*)2) and recursively call the algorithm on Qn-2(x).
While discovering each root, it must be accumulated in a data structure and if it is complex, its conjugate must also be added.
In the second phase of the project, you are required to write a program that can find the global minimum of an even degree polynomial. The program must follow these steps:
Step 1: Calculate the derived polynomial.
Step 2: Find the roots of the derived polynomial using the program from phase one.
Step 3: Extract the real roots from the derived polynomial.
Step 4: Evaluate the polynomial at each real root to find the minimum value.
Step 5: The minimum value of the polynomial at these points is the global minimum.
Overall, this project requires you to have a good understanding of polynomials, roots, and recursion. The project also requires you to implement various numerical methods, such as bisection method, regula falsi, and Newton's method.
The recursive solution method has the following steps:
Step 1: If the degree of the polynomial Pn(x) is less than or equal to 4, use the solve_p4c.c program to find the roots.
Step 2: If the degree of the polynomial Pn(x) is even, find a segment (a,b) where Pn(a)Pn(b) < 0. You can calculate Pn(0) to determine which value to use for a and b. Then use the bisection method or the bisection method with regula falsi to find a real root x. After finding x*, do a long division of Pn(x) by (x-x*) and recursively call the algorithm on Qn-1(x).
Step 3: If the degree of the polynomial Pn(x) is odd, use Newton's complex method to find a root x* which may be complex x*=a*+bi. If x turns out to be real (b in absolute value is less than epsilon), do a long division of Pn(x) by (x-a*) and recursively call the algorithm on Qn-1(x). If x* turns out to be complex, do a long division of Pn(x) by (x2-2ax2+(a)2+(b*)2) and recursively call the algorithm on Qn-2(x).
While discovering each root, it must be accumulated in a data structure and if it is complex, its conjugate must also be added.
In the second phase of the project, you are required to write a program that can find the global minimum of an even degree polynomial. The program must follow these steps:
Step 1: Calculate the derived polynomial.
Step 2: Find the roots of the derived polynomial using the program from phase one.
Step 3: Extract the real roots from the derived polynomial.
Step 4: Evaluate the polynomial at each real root to find the minimum value.
Step 5: The minimum value of the polynomial at these points is the global minimum.
Overall, this project requires you to have a good understanding of polynomials, roots, and recursion. The project also requires you to implement various numerical methods, such as bisection method, regula falsi, and Newton's method.