Implementation of numerical methods for the solution of nonlinear equations.

How to compile

As the Eigen/Dense library is added at a submodule, the first thing to do is to populate it before anything else. You can do this by running the following command in the terminal of the main project:

git submodule update --init eigen

All other libraries (muparser, googletest) are added as subtrees, so they will already be 'filled' and ready to be used.

Next, the CMakeLists.txt is already properly configured (with all libraries linked, ...) to compile & build the project. Either use the build interface (button top right) that is provided in Clion or navigate into the cmake-build-debug directory and run the following commands:

cd cmake-build-debug

cmake ..
make

If there is no cmake-build-debug directory, please create one, running the commands as follows (in the main dir terminal):

mkdir cmake-build-debug
# move into the dir to make the executables
cd cmake-build-debug

cmake ..
make

If any errors (e.g. Makefile is not found) occur, please delete the CMakeCache.txt and try running both commands again.

Program execution (flow) & usage

Program Flow

Users can interact with the central file central_exec.cpp through input files (the pre-provided input*.txt files or a personal config.txt file that they can fill in themselves). When running the executable with the commands mentioned above, the main() function receives this .txt containing all the essential arguments to solve a non-linear problem.

Looking at the code, a typical execution of the program is split into three parts:

1. PROCESS THE INPUT : Upon execution (if an existing .txt file is inputted) the ConfigFileReader class is instantiated. It receives the .txt file, reads & parses it and saves all inputs in their respective fields. The main(), as well as other function when passed the instance, can then access these fields through getter functions to find out the requested method & its associated data. Additional checks are performed to see if input matches up with what is expected (see also *Rules & conventions to follow when filling in config.txt). If not, an error is returned.

After, we can invoke an instance of the Solver class and run one of the provided *Input() functions to get our input as the right class (either MonoFunction or System), which is once again based on the arguments given in the config file.

2. EXECUTE THE METHOD : Once we determined the method & the inputs, we move on to the second phase, the actual calculations. We create a pointer p to a Method object, which uses getMethod() to create an instance of the appropriate method class. The possibility of using Aitken acceleration (if applicable) is also factored in here.

Next, we use the input created with the solve instance to feed into this pointer's operator (overloaded), together with other relevant arguments, and actually perform the method. What we get back is a Solution class which encapsulates all the results of the method.

3. PRINT THE OUTPUT : Lastly, we can actually output the results with a function inside the Solution class. We once again feed the ConfigFileReaderinto it so it is tailored to the specific arguments, and get a concise and clean summary of the method & its results in the terminal.

Usage

If properly compiled, up-to-date executables have been built for both main_exec and test_suite. They can now be run/used as follows, where the * can be replaced by a number 1 - 9 to run a different provided input file. All inputs can be found in the input_config directory.

# run test suite
./test_suite

# run main executable for one of the provided inputs (* = 1 - 9)
./main_exec --config ../input_config/input*.txt

To use the program for your own calculations or input, head over to the config.txt file in the main directory and fill in the provided fields (conventions & rules are mentioned just below). When the config-file is changed, there is no need to re-run or re-build anything. Simply use the command mentioned below and main_exec will re-run for the updated fields.

# run main executable for your own input
./main_exec --config ../config.txt

In both cases, if the input is of the proper format, the output (= the results of the problem) will be printed into the terminal, in a clean & concise way. Then, you can just run it again with a different file or after having edited the fields.

restrictions & conventions to follow when filling in config.txt :

please note: our project follows mu::parser conventions (e.g. x^2 instead of std::pow(x,2))

As an example, this is what the config.txtfile could look like to execute the Newton method for Systems (more examples can be found in the input_configdirectory):

# General settings
function = x^2 + y^2 - 10 | x*y-5
variables = x | y
fixed_point =
derivative = 2*x | 2*y | y | x

# Method settings
algorithm = SN
aitken = no
tolerance = 1e-10
max_iterations = 1e3
start_point = 2.1 , 2.0

and this is what is returned in the terminal:

Method was run with Aitken acceleration
The root 24.738633753705965 was found in 6 iterations. 

This is an overview of the results:
------------------------------ 
Iterations : 6
Converged : YES
Start point : 20.708496732026145
Iteration 1: 28.829752066115702
Iteration 2: 24.451722931404831
Iteration 3: 24.736950595846789
Iteration 4: 24.738633696443035
Iteration 5: 24.738633753705962
Iteration 6: 24.738633753705965
------------------------------ 

Features

• Multiple Numerical Methods: Implements various numerical methods like Newton's Method, Bisection Method, Chord Method, and Fixed Point Iteration.
• Support for Different Functions: Capable of handling a wide range of mathematical functions, including polynomials, trigonometric functions, and exponential functions.
• Precision Control: Allows users to set the desired level of accuracy for the root finding process.
• Convergence Verification: Checks and verifies the convergence (to an actual root, not just a fixed point) of the selected method for the given function.
• Error Handling: Implements a number of error handling mechanisms to manage non-converging scenarios and input errors.
• Detailed Output: Outputs detailed step-by-step calculations.
• Extensive Documentation: Comes with comprehensive documentation covering usage instructions and method explanations.

Tests

Majority of the tests are designed to validate the correctness and robustness of different numerical methods or in the project, by testing the convergence and accuracy of the root and the final function evaluation. Along with this, there are tests that focus on the instantiation & validity of Function & System classes, as well as ones that check if the ConfigFileReader behaves as expected.

Accelerable methods (Newton, FixedPoint) are also tested with Aitken acceleration, performing additional checks to make sure this acceleration acutally yields better results (faster convergence, fewer iterations).

Tests are using the Solver interface to call up 'fixtures', which enables us to write them in a short way. Along with this, we simply create 1 Solver instance which can be reused throughout the test.

Example :

    Solver solver;

    Solution test1 = solver.NewtonMethod("x^2 - 612", "2 * x", 1.0, 1e-10, 1000);
    EXPECT_TRUE(test1.hasConverged());
    ASSERT_NEAR(24.73863375370596329892846, test1.getRoot(), 1e-8);
    ASSERT_NEAR(0, solver.EvaluateFunction("x^2 - 612", test1.getRoot()), 1e-10);
    

Method tests

NewtonTest

Converging Tests

• NewtonTest, Converging checks convergence and accuracy for these equations, as well as for their accelerated versions:
  • x^2 - 612
  • cos(x) - x^3
  • x^2 - 2
  • x/(1+x^2)

Diverging Tests

• NewtonTest, Diverging checks non-convergence for these equations:
  • x^(1/3)
  • x/(1+x^2)

System Tests

• NewtonTest, System checks convergence and accuracy for these systems of equations:
  • f(x,y) = (x^2 + y^2 -10, x*y -5)
  • f(x,y) = (x^2 + y^2 -1, e^(x*y) - sin(y))

FixedPointTest

Converging Tests

• FixedPointTest, Converging checks convergence and accuracy for these equations, as well as for their accelerated versions:
  • x^4 - x - 10
  • cos(x) - (x * exp(x))
  • x - sin(x) - (1/2)

Diverging Tests

• FixedPointTest, Diverging assesses non-convergence for f(x) = x^4 - x - 10, with different x = g(x):
  • 10/(x^3-1)
  • sqrt(x+10)/x

ChordTest

Converging Tests

• ChordTest, Converging checks convergence and accuracy for these equations:
  • x^2 - 612
  • x^3 - x - 1
  • exp(-x) - x

Diverging Tests

• ChordTest, Diverging checks non-convergence for these equations:
  • log(x)
  • tan(x)

BisectionTest

Converging Tests

• BisectionTest, Converging checks convergence and accuracy for these equations:
  • x^3 - x - 2, 10 - x^2, -x - exp(-x).

Diverging Tests

• BisectionTest, Diverging checks non-convergence for these equations:
  • x - exp(-x)
  • 10 - x^2

InputTest

• InputTest, MonoFunction checks function(with only one variable), fixed-point and derivative evaluation.
• InputTest, MultiFunction checks function(multi variables) evaluation and partial derivatives.
• InputTest, System checks system of equations evaluation and Jacobian.

ConfigFile

• ConfigFile, Inputs checks that are all inputs are read correctly
• ConfigFile, Errors checks that errors are correctly handed

Documentation

All classes & functions are documented using Doxygen. In order to launch the Doxygen html page of this project, just execute the following command in the main directory:

open doxygen_documentation/html/index.html

Limitations, Perspectives & TODOs, and Problems

1. Limitation : Error Handling. The project currently uses a basic approach to error handling, mainly throwing std::runtime_errors without sophisticated catching mechanisms. This can cause the problem (as we actually noticed during the project) of having to 'figure out what's wrong' ourselves, without any feedback. After this, we tried adding more comprehensive error reporting, but it is still lacking due to time constraints.

► TODO Ideally, implement a layered error handling that includes exception categorization, detailed error logging, and user-friendly messages for very nuanced errors. Additionally, It would be nice to consider having a fallback mechanism to maintain system stability in case of critical failures.

2. Limitation : Input Validation. The project lacks extensive input validation, which might lead to unexpected results with incorrect inputs. Instead, it heavily relies on the user filling in the config.txt file in exactly the way it expects. There are few mechanisms/checks in place (e.g. to check if the method is a valid one), but we could do with more of them.

► TODO Comprehensive input validation would be a valuable addition for enhancing the project's reliability. Along with this, it would also be nice to be more lax towards the way the user fills out the file & be able to deal with more ways of input. Ideally, we would have both a very strong input validation, and more flexibility in what we see as valid inputs.

3. Limitation : Input File Types. Right now the Input format is constrained to a .txt file, and it can only handle 1 request to solve a non-linear problem in each file. This was chosen because a .txt file is the easiest to parse without using additional libraries, and it also the simplest to just consider 1 request at a time.

► TODO Expanding the program to accept various input file formats could increase its versatility. Besides this, Allowing for multiple requests / inputs in 1 config file (and having them all processed) could also help the project to become more user-friendly & meaningful, as it would e.g. allow for a user to run the same problem with different methods easily, get all the results back at once (sorted if needed) and compare them when it comes to performance, ... in order to choose the best algorithm for the specific problem.

4. Limitation : Output Options. Currently, the program's output is limited to the results (root, iterations, ...) being printed in the terminal, which is straightforward to implement and was a good additional way of testing If our program works as expected, but it lacks flexibility and sophistication. This limitation means that users cannot easily visualize results, integrate with other tools, or receive outputs in a format best suited for their needs.

► TODO Offer multiple ways of outputting solutions, to cater to a wider range of user requirements. We could implement features such as exporting results to different file formats (e.g., txt, CSV, JSON, XML), generate HTML pages to present the data in a more engaging way or integrate with visualisation tools such as Gnuplot, enhancing the project's usability.