Implementation of numerical methods for the solution of nonlinear equations.

How to compile

As the Egigen/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:

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.

Like this, up-to-date executables have been built for both main_exec and test_suite. They can now be run as follows, where the * can be replaced by a number 1 - 9 to run a different input file. All inputs can be found in the config_files.

# 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 in the Program execution & usage section). 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

Program execution (flow) & usage

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.

Following this, a typical execution of the program goes as follows:

1. Reading the data: Upon execution, the ConfigFileReader class is instantiated. It receives the .txt file, reads & parses it and saves all inputs in their respective fields. The main() 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.

2. Computing the request: Once we determined the method & the inputs, we move on to the actual calculations by invoking an instance the Solver class. This class provides interfaces for each implemented method. We call the relevant interface and pass it the needed inputs as arguments, directly from the ConfigFileReader class. Within this function call:

   • A MonoFunction/System (of Multifunctions) class is instantiated with the provided equations.
   • An instance of the relevant method's class is created. If Aitken acceleration is requested for an accelerable method, the Aitken class is initialized, taking the normal method's class as input.
   • The method performs the iterations on the inputted function/system and other arguments. The result is encapsulated in a Solution class and returned to main();

The method might call upon private helper functions within the class during the computation to aid with calculations. If Aitken acceleration is performed on a method, it is these same helper functions (init, step, ...) that are accessed and utilized by the Aitken class to avoid redundant code.

3. Outputting the Solution: Back in main(), we then invoke one of the *Output() functions in the Solver class. It is provided with the obtained root as well some additional strings as input. These functions and strings allow for a clean & consistent output format, as they do not depend on the method that was used to get the root. The enum(eration) class MethodType is used to easily determine the output format depending on the method used.

error handling

USAGE ?

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
------------------------------ 

List of features & tests

Features

• Newton Solver using Newton method, can be used for a function or a system of functions.
• FixedPoint Solver using fixed point method, used on functions.
• Chord Solver using the chord method,used on functions.
• Bisection Solver using the Bisection method, used on functions.
• Aitken Accelerator that can accelerate Newton and FixedPoint using Aitken Acceleration.

Tests

Each test is designed to validate the correctness and robustness of different numerical methods in the project, by testing the convergence and accuracy of the root and the final function evaluation.

Accelerable methods(Newton, FixedPoint) are also tested with Aitken acceleration, where there is also a faster convergence check.

Tests are using the Solver interface which enables us to write them in a short way.

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:
  • 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:
  • 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

How to launch Doxygen

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